Helena Bergold ; Winfried Hochstättler ; Uwe Mayer - The Neighborhood Polynomial of Chordal Graphs

dmtcs:8388 - Discrete Mathematics & Theoretical Computer Science, May 6, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.8388
The Neighborhood Polynomial of Chordal Graphs

Authors: Helena Bergold ; Winfried Hochstättler ; Uwe Mayer

We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor. We introduce a parameter for chordal graphs called anchor width and an algorithm to compute the neighborhood polynomial which runs in polynomial time if the anchor width is polynomially bounded. The anchor width is the maximal number of different sub-cliques of a clique which appear as a common neighborhood. Furthermore we study the anchor width for chordal graphs and some subclasses such as chordal comparability graphs and chordal graphs with bounded leafage. the leafage of a chordal graphs is the minimum number of leaves in the host tree of a subtree representation. We show that the anchor width of a chordal graph is at most $n^{\ell}$ where $\ell$ denotes the leafage. This shows that for some subclasses computing the neighborhood polynomial is possible in polynomial time while it is NP-hard for general chordal graphs.

Volume: vol. 24, no. 1
Section: Graph Theory
Published on: May 6, 2022
Accepted on: April 22, 2022
Submitted on: August 25, 2021
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C31 05C85


Consultation statistics

This page has been seen 234 times.
This article's PDF has been downloaded 250 times.