In 2022, Artes et al. [3] introduced a bivariate graph polynomial called the clique common neighborhood polynomial of a graph. In this paper, we extended the idea to connected common neighborhood system by restricting to the maximum connected subset of the common neighborhood system of a clique in a graph. Moreover, we establish the clique connected common neighborhood polynomials of complete bipartite graphs and complete q-partite graphs.

clique, clique polynomial, clique common neighborhood polynomial, clique connected common neighborhood polynomial.

Received: February 7, 2023; Accepted: March 11, 2023; Published: March 22, 2023

How to cite this article: Amelia L. Arriesgado, Sonny C. Abdurasid and Rosalio G. Artes, Jr., Connected common neighborhood systems of cliques in a graph: a polynomial representation, Advances and Applications in Discrete Mathematics 38(1) (2023), 69-81. http://dx.doi.org/10.17654/0974165823019

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

References:

[1] N. Abdulcarim, S. Dagondon and E. Chacon, On the independent neighborhood polynomial of the Cartesian product of some special graphs, Eur. J. Pure Appl. Math. 14(1) (2021), 173-191.
[2] R. Artes and L. Laja, Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923.
[3] R. Artes, M. Langamin and A. Calib-og, Clique common neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 35 (2022), 77-85.
[4] J. Brown and R. Nowakowski, The neighborhood polynomial of a graph, Australas. J. Combin. 42 (2008), 55-68.
[5] J. Ellis-Monaghan and J. Merino, Graph Polynomials and their Applications II: Interrelations and Interpretations, Birkhauser, Boston, 2011.
[6] I. Gutman, Graphs and graph polynomials of interest in chemistry, Gottfried Tinhofer and Gunther Schmidt, eds., Lecture Notes in Computer Science, Berlin, Springer-Verlag, 2005, pp. 177-187.
[7] F. Harary, Graph Theory, CRC Press, Boca Raton, 2018.
[8] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994), 219-228.
[9] U. S. R. Murty and J. A. Bondy, Graph Theory and Related Topics, Academic Press, New York, 1979.
[10] J. Yellen and J. L. Gross, Graph Theory and its Applications, Chapman & Hall, New York, 2006.