Let G be a connected graph of order n. A convex subgraph of G is any subgraph induced by a convex subset S of  The convex subgraph polynomial of G is the polynomial  where  is the number of convex subgraphs of G of order i. This study revisits the paper on convex subgraph polynomials discussed in [6, 7, 9]. Specifically, this establishes results relating the convex subgraph polynomial of some nth order graph and  order and determines the convex subgraph polynomials of the path and cycle as well as their complements. Some values of some graph parameters which are actually values of convex subgraph polynomials at specific points were identified. It is also shown that for every integer k, there is a connected graph G for which C(G, -1) = k.

convex sets, convex subgraph polynomial, important values.

Received: October 27, 2023; Accepted: December 21, 2023; Published: January 5, 2024

How to cite this article: Ladznar S. Laja, On convex subgraph polynomials and some of its important values, Advances and Applications in Discrete Mathematics 41(1) (2024), 57-76. http://dx.doi.org/10.17654/0974165824004

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] Jason I. Brown and Richard Hoshino, Independence polynomials of circulants with an application to music, Discrete Math. 309 (2009), 2292-2304.
[2] Sergio R. Canoy, Jr. and I. J. L. Garces, Convex sets under some graph operations, Graph and Combinatorics 18 (2002), 787-793.
[3] S. R. Canoy, Jr. and L. S. Laja, Convex sets in the corona and conjunction of graphs, Congr. Numer. 180 (2006), 207-217.
[4] Hajiabolhassan Mehrabadi, On clique polynomials, Australian Journal of Combinatorics 18 (1998), 313-316.
[5] F. Harary and J. Nieminen, Convexity in graphs, J. Differential Geom. 16(2) (1981), 185-190.
[6] Ladznar S. Laja and Rosalio G. Artes, Jr., Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923.
[7] Ladznar S. Laja and Rosalio G. Artes, Jr., Convex subgraph polynomials of the join and the composition of graphs, International Journal of Mathematical Analysis 10(11) (2016), 515-529.
[8] Ladznar S. Laja and Aziz B. Tapeing, Co-segregated polynomial of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 101-112.
[9] Ladznar S. Laja, Convex subgraph polynomials of degree 3 or 4, rooted and co-normal products of graphs, Advances of Applications in Discrete Mathematics 41(1) (2024), 27-40.
[10] Vadim E. Levit and Eugen Mandrescu, Independence polynomials of a graph - a survey, Proceedings of the 1st International Conference on Algebraic Informatics, Greece, 2005, pp. 233 254.
[11] A. B. Tapeing, L. S. Laja, J. A. Hassan and H. B. Copel, Totally segregated polynomial of graphs, Advances of Applications in Discrete Mathematics 40(2) (2023), 213-223.