The idea of polynomial representation describing a graph using a specified substructure with a corresponding neighborhood system was first introduced by Artes et al. [20] by considering the common neighborhood systems of cliques in a graph. In this paper, we introduce the notion of a convex neighborhood polynomial for a  graph and establish some of its properties. Moreover, we investigate the convex neighborhood polynomials of some special graphs such as paths, cycles, complete graphs, and complete bipartite graphs. More interestingly, we have shown that the convex neighborhood polynomial of a path can be expressed as a linear combination of  the elements of {1, f(x), f'(x)} for some nth partial sum f(x) of a geometric series.

convex set1, neighborhood system, convex neighborhood polynomial.

Received: June 29, 2023; Accepted: August 14, 2023; Published: August 25, 2023

How to cite this article: Sonny C. Abdurasid, Bayah J. Amiruddin, Jeffrey Imer C. Salim and Rosalio G. Artes Jr., Convex neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 125-137. http://dx.doi.org/10.17654/0974165823061

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, Int. J. Math. Comput. Sci. 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, Appl. Math. Sci. 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, Appl. Math. Sci. 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, Glob. J. Pure Appl. Math. 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, Australas. J. Combin. 42 (2008), 55-68.
[16] J. Ellis-Monaghan and J. Merino, Graph Polynomials and their Applications II: Interrelations and Interpretations, Birkhauser, Boston, 2011.
[17] F. Harary, Graph Theory, CRC Press, Boca Raton, 2018.
[18] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994), 219-228.
[19] 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.
[20] Rosalio G. Artes, Jr., Mercedita A. Langamin and Almira B. Calib-og, Clique common neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 35 (2022), 77-85. https://doi.org/10.17654/0974165822053.
[21] L. S. Laja and R. G. Artes Jr., Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923. http://dx.doi.org/10.12988/ams.2014.44285.
[22] 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.
[23] 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.