Let G be a simple connected graph. Then an i-subset of V(G) is a subset of V(G) of cardinality i. An i-clique is an i-subset which induces a complete subgraph of G. The clique neighborhood polynomial of G is given by where c_ij(G) is the number of i-cliques in G with neighborhood cardinality equal to j and ω(G) is the cardinality of a maximum clique in G, called the clique number of G. In this paper, we obtain the clique neighborhood polynomials of the special graphs such as the complete graph, complete bipartite graph and complete q-partite graph using combinatorial approach.

clique, neighborhood system, clique neighborhood polynomial.

Received: September 14, 2023; Accepted: October 9, 2023; Published: October 21, 2023

How to cite this article: Alcyn R. Bakkang, Regimar A. Rasid and Rosalio G. Artes, Jr., Combinatorial approach in counting the neighbors of cliques in a graph, Advances and Applications in Discrete Mathematics 40(2) (2023), 167-175. http://dx.doi.org/10.17654/0974165823063

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. https://doi.org/10.29020/nybg.ejpam.v14i1.3860.
[2] R. A. Anunciado and R. G. Artes, Jr., Connected dominating independent neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 39(1) (2023), 73-80. https://doi.org/10.17654/0974165823036.
[3] A. L. Arriesgado and R. G. Artes, Jr., Convex independent common neighborhood polynomial of a graph, Advances and Applications in Discrete Mathematics 38(2) (2023), 145-158. https://doi.org/10.17654/0974165823025.
[4] A. L. Arriesgado, S. C. Abdurasid and R. 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. https://doi.org/10.17654/0974165823019.
[5] A. L. Arriesgado, J. I. C. Salim and R. G. Artes, Jr., Clique connected common neighborhood polynomial of the join of graphs, International Journal of Mathematics and Computer Science 18(4) (2023), 655-659.
[6] R. G. Artes, Jr., N. H. R. Mohammad, A. A. Laja and N. H. M. Hassan, From graphs to polynomial rings: star polynomial representation of graphs, Advances and Applications in Discrete Mathematics 37 (2023), 67-76.
https://doi.org/10.17654/0974165823012.
[7] R. G. Artes, Jr., A. J. U. Abubakar and S. U. Kamdon, Polynomial representations of the biclique neighborhood of graphs, Advances and Applications in Discrete Mathematics 37 (2023), 37-45. http://dx.doi.org/10.17654/0974165823010.
[8] R. G. Artes, Jr. and M. J. F. Luga, Convex accessibility in graphs, Applied Mathematical Sciences 8(88) (2014), 4361-4366.
http://dx.doi.org/10.12988/ams.2014.46467.
[9] R. G. Artes, Jr. and M. J. F. Luga, Convex accessibility in graph operations, Applied Mathematical Sciences 8(116) (2014), 5763-5770.
http://dx.doi.org/10.12988/ams.2014.47553.
[10] R. G. Artes, Jr., N. H. R. Mohammad, Z. H. Dael and H. B. Copel, Star polynomial of the corona of graphs, Advances and Applications in Discrete Mathematics 39(1) (2023), 81-87. https://doi.org/10.17654/0974165823037.
[11] R. G. Artes, Jr., R. H. Moh. Jiripa and J. I. C. Salim, Connected total dominating neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 39(2) (2023), 145-154. http://dx.doi.org/10.17654/0974165823042.
[12] R. G. Artes, Jr. and J. B. Nalzaro, Combinatorial approach for counting geodetic sets with subdominating neighborhoods systems, Advances and Applications in Discrete Mathematics 38(2) (2023), 179-189.
https://doi.org/10.17654/0974165823027.
[13] R. G. Artes, Jr. and R. A. Rasid, Balanced biclique polynomial of graphs, Global Journal of Pure and Applied Mathematics 12(5) (2016), 4427-4433.
[14] R. G. Artes, Jr. and R. A. Rasid, Combinatorial approach in counting the balanced bicliques in the join and corona of graphs, Journal of Ultra Scientist of Physical Sciences 29(5) (2017), 192-195.
[15] J. I. Brown and R. J. Nowakowski, The neighbourhood polynomial of a graph, Australian Journal of Combinatorics 42 (2008), 55-68.
[16] J. Ellis-Monaghan and J. Merino, Graph Polynomials and their Applications II: Interrelations and Interpretations, Birkhauser, Boston, 2011.
[17] E. J. Farell, A note on the clique polynomial and its relation to other graph polynomials, J. Math. Sci. Calcutta 8 (1997), 97-102.
[18] F. Harary, Graph Theory, CRC Press, Boca Raton, 2018.
[19] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Mathematics 125 (1994), 219-228.
[20] R. E. Madalim, R. G. Eballe, A. H. Arajaini and R. G. Artes, Jr., Induced cycle polynomial of a graph, Advances and Applications in Discrete Mathematics 38(1) (2023), 83-94. https://doi.org/10.17654/0974165823020.
[21] M. A. Langamin, A. B. Calib-og and R. G. Artes, Jr., Clique common neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 35 (2022), 77-85. https://doi.org/10.17654/0974165822053.
[22] L. S. Laja and R. G. Artes, Jr., Zeros of convex subgraph polynomials, Applied Mathematical Sciences 8(59) (2014), 2917-2923.
http://dx.doi.org/10.12988/ams.2014.44285.
[23] 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. http://dx.doi.org/10.12988/ijma.2016.512296.
[24] C. A. Villarta, R. G. Eballe and R. G. Artes, Jr., Induced path polynomial of graphs, Advances and Applications in Discrete Mathematics 39(2) (2023), 183-190. https://doi.org/10.17654/0974165823045.
[25] A. Vijayan and K. D. Vijila, On geodetic sets and polynomials of centipedes, International Journal of Mathematical Archive 3(5) (2012), 1885-1894.
[26] Y. Wang and B. Zhu, On the unimodality of independence polynomials of some graphs, European Journal of Combinatorics 30 (2011), 10-20.