Geodesic
Graph Operations and Neighborhood Polynomials
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 697-711.

Voir la notice de l'article provenant de la source Library of Science

The neighborhood polynomial of graph G is the generating function for the number of vertex subsets of G of which the vertices have a common neighbor in G. In this paper, we investigate the behavior of this polynomial under several graph operations. Specifically, we provide an explicit formula for the neighborhood polynomial of the graph obtained from a given graph G by vertex attachment. We use this result to propose a recursive algorithm for the calculation of the neighborhood polynomial. Finally, we prove that the neighborhood polynomial can be found in polynomial-time in the class of k-degenerate graphs.
Keywords: neighborhood complex, neighborhood polynomial, domination polynomial, graph operations, graph degeneracy 
@article{DMGT_2021_41_3_a0,
     author = {Alipour, Maryam and Tittmann, Peter},
     title = {Graph {Operations} and {Neighborhood} {Polynomials}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {697--711},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a0/}
}
TY  - JOUR
AU  - Alipour, Maryam
AU  - Tittmann, Peter
TI  - Graph Operations and Neighborhood Polynomials
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 697
EP  - 711
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a0/
LA  - en
ID  - DMGT_2021_41_3_a0
ER  - 
%0 Journal Article
%A Alipour, Maryam
%A Tittmann, Peter
%T Graph Operations and Neighborhood Polynomials
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 697-711
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a0/
%G en
%F DMGT_2021_41_3_a0
Alipour, Maryam; Tittmann, Peter. Graph Operations and Neighborhood Polynomials. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 697-711. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a0/

[1] S. Akbari, S. Alikhani and Y.-h. Peng, Characterization of graphs using domination polynomials, European J. Combin. 31 (2010) 1714–1724. doi:10.1016/j.ejc.2010.03.007

[2] A. Andrzejak, Splitting formulas for Tutte polynomials, J. Combin. Theory Ser. B 70 (1997) 346–366. doi:10.1006/jctb.1997.1767

[3] J.L. Arocha and B. Llano, Mean value for the matching and dominating polynomials, Discuss. Math. Graph Theory 20 (2000) 57–69. doi:10.7151/dmgt.1106

[4] A.E. Brouwer, P. Csorba and A. Schrijver, The number of dominating sets of a finite graph is odd (2009). https://www.win.tue.nl/~aeb/preprints/domin4a.pdf

[5] J.I. Brown and R.J. Nowakowski, The neighbourhood polynomial of a graph, Australas. J. Combin. 42 (2008) 55–68.

[6] M. Dod, The independent domination polynomial. arXiv preprint arXiv:1602.08250 (2016).

[7] K. Dohmen and P. Tittmann, Domination reliability, Electron. J. Combin. 19 (2012) #P15. doi:10.37236/1166

[8] J. Flum and M. Grohe, The parameterized complexity of counting problems, SIAM J. Comput. 33 (2004) 892–922. doi:10.1137/S0097539703427203

[9] B.S. Gubser, A characterization of almost-planar graphs, Combin. Probab. Comput. 5 (1996) 227–245. doi:10.1017/S0963548300002005

[10] I. Heinrich and P. Tittmann, Neighborhood and domination polynomials of graphs, Graphs Combin. 34 (2018) 1203–1216. doi:10.1007/s00373-018-1968-7

[11] S. Kijima, Y. Okamoto and T. Uno, Dominating set counting in graph classes, in: Proc. 17th Annual International Conference, COCOON 2011, Lecture Notes in Comput. Sci. 6842 (2011) 13–24. doi:10.1007/978-3-642-22685-4_2

[12] T. Kotek, J. Preen, f. Simon, P. Tittmann and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, Electron. J. Combin. 19 (2012) #P47. doi:10.37236/2475

[13] T. Kotek, J. Preen and P. Tittmann, Subset-sum representations of domination polynomials, Graphs Combin. 30 (2014) 647–660. doi:10.1007/s00373-013-1286-z

[14] T. Kotek, J. Preen and P. Tittmann, Domination polynomials of graph products. arXiv preprint arXiv:1305.1475 (2013)

[15] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978) 319–324. doi:10.1016/0097-3165(78)90022-5