论文标题
HARARY多项式
Harary polynomials
论文作者
论文摘要
给定一个Graph属性$ \ MATHCAL {P} $，F。HARARY在1985年$ \ Mathcal {p} $ - 颜色，图形颜色，每个大要素在$ \ Mathcal {p} $中诱导图形。令$χ_ {\ Mathcal {p}}}（g; k）$计数$ \ Mathcal {p} $ - $ g $的颜色，最多是$ k $ colors。事实证明，$χ_ {\ Mathcal {p}}}（g; k）$是$ \ Mathbb {z} [z} [k] $的多项式。该形式的多项式图称为Harary多项式。在本文中，我们研究了Harary多项式的特性，并将它们与经典色度多项式$χ（G; K）$的特性进行了比较。我们表明，特征性和拉普拉斯多项式，匹配，独立性和统治多项式不是Harary多项式。我们表明，对于各种稀疏，非平凡属性的概念$ \ MATHCAL {p} $，多项式$χ_ {\ Mathcal {p}}}}（g; k）$与$χ（g; k; k）$相反，而不是一个色度消除式无风度。最后，我们研究了harary多项式是否可以在单层二阶逻辑中定义。
Given a graph property $\mathcal{P}$, F. Harary introduced in 1985 $\mathcal{P}$-colorings, graph colorings where each colorclass induces a graph in $\mathcal{P}$. Let $χ_{\mathcal{P}}(G;k)$ counts the number of $\mathcal{P}$-colorings of $G$ with at most $k$ colors. It turns out that $χ_{\mathcal{P}}(G;k)$ is a polynomial in $\mathbb{Z}[k]$ for each graph $G$. Graph polynomials of this form are called Harary polynomials. In this paper we investigate properties of Harary polynomials and compare them with properties of the classical chromatic polynomial $χ(G;k)$. We show that the characteristic and Laplacian polynomial, the matching, the independence and the domination polynomial are not Harary polynomials. We show that for various notions of sparse, non-trivial properties $\mathcal{P}$, the polynomial $χ_{\mathcal{P}}(G;k)$ is, in contrast to $χ(G;k)$, not a chromatic, and even not an edge elimination invariant. Finally we study whether Harary polynomials are definable in Monadic Second Order Logic.
