论文标题
和弦图的邻居多项式
The Neighborhood Polynomial of Chordal Graphs
论文作者
论文摘要
我们研究邻域多项式及其对弦图的计算的复杂性。图的邻域多项式是其具有共同邻居的顶点子集的生成函数。我们引入了一个称为锚固宽度的和弦图的参数和一个算法，以计算邻居多项式，如果锚宽度是多项式界限的，则在多项式时间内运行。锚固宽度是作为一个公共邻里的集团的不同子信号的最大数量。此外，我们研究了弦图的锚宽度和一些子类，例如带有有界叶片的弦可比性图和弦图。和弦图的叶片是子树表示的主机树中的最小叶子数。我们表明，和弦图的锚固宽度最多是$ n^{\ ell} $，其中$ \ ell $表示叶子。这表明，对于某些子类，计算邻域多项式的多项式可能是多项式多项式的，而对于一般的和弦图是NP的。
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.
