A convex subgraph of a connected graph G of order n is a subgraph  induced by a convex subset S of  The convex subgraph polynomial of G is the polynomial

where c_i(G) is the number of convex subgraphs of G of order i. This study enumerates all possible convex subgraph polynomials having degree 3 or 4. This also characterizes a convex set in the rooted product  and the co-normal product  The convex subgraph polynomials of these graph operations are also established.

convex set, convex subgraph polynomial.

Received: October 12, 2023; Revised: November 24, 2023; Accepted: December 5, 2023; Published: December 9, 2023

How to cite this article: Ladznar S. Laja, Convex subgraph polynomials of degree 3 or 4, rooted and co-normal products of graphs, Advances and Applications in Discrete Mathematics 41(1) (2024), 27-40. http://dx.doi.org/10.17654/0974165824002

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

References:
[1] J. Caceres, O. R. Oellermann and M. L. Puertas, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory 32 (2012), 685-704.
[2] S. R. Canoy, Jr., G. Cagaanan and S. V. Gervacio, Convexity, geodetic and Hull numbers of the join of graphs, Util. Math. 71 (2006), 143 159.
[3] S. R. Canoy, Jr. and I. J. L. Garces, Convex sets under some graph operations, Graphs Combin. 18 (2002), 787-793.
[4] S. R. Canoy, Jr. and L. S. Laja, Convex sets in the corona and conjunction of graphs, Congr. Numer. 180 (2006), 207-216.
[5] G. Chartrand, J. F. Fink and P Zhang, Convexity in oriented graphs, Discrete Appl. Math. 116 (2002), 115-126.
[6] M. C. Dourado, F. Protti and J. L. Szwarcfiter, Complexity results related to monophonic convexity, Discrete Appl. Math. 158 (2010), 1268-1274.
[7] C. D. Godsil and B. D. Mckay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978), 21-28.
[8] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994), 219-228.
[9] L. S. Laja and R. G. Artes, Jr., Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923.
[10] L. S. Laja and R. G. Artes, Jr., Convex subgraph polynomials of the join and the composition of graphs, International Journal of Mathematical Analysis 10(11) (2016), 515-529.
[11] A. B. Tapeing and L. S. Laja, Co-segregated polynomial of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 101-112.
[12] Francesco M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Elsevier Discrete Mathematics 309 (2009), 4287-4298.
[13] A. P. Santhakumaran and S. V. Ullas Chandran, On the vertex detour hull numbers of a graph, J. Indones. Math. Soc. 20(1) (2014), 1-9.
[14] A. P. Santhakumaran and P. Titus, The connected vertex detour number of a graph, Acta Univ. Sapientiae Math. 2 (2010), 146-159.
[15] D. M. Tuan and V. D. Hoa, Quasi - strongly regularity of co-normal product, 2018, pp. 458-464. DOI: 10.15625/vap.2018.00060.