- Tytuł:
- Graph Operations and Neighborhood Polynomials
- Autorzy:
-
Alipour, Maryam
Tittmann, Peter - Powiązania:
- https://bibliotekanauki.pl/articles/32083862.pdf
- Data publikacji:
- 2021-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
neighborhood complex
neighborhood polynomial
domination polynomial
graph operations
graph degeneracy - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 697-711
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł