Evaluations of Graph Polynomials
Evaluations of Graph Polynomials
复制标题
图多项式的计算
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Makowsky
中科院分区：
文献类型：
--
作者：
Benny Godlin;Tomer Kotek;J. Makowsky
图多项式$p(G，ar{X})$可以用各种方式编码关于基础图G的数值信息：作为它的度、作为它的特定系数之一或作为在特定点的求值$ar{X}=ar{x}_0$。本文研究了如何证明一个给定的图参数，即G的最大团的大小*(G)不是一个固定的系数，也不能是Tutte多项式、交错多项式或某无穷图多项式的任何图多项式在任何一点的赋值。
我们的结果是非常普遍的。给出了图参数f(G)的关联矩阵的一个充分条件，即f(G)不可能是CMSOL中不变定义的任何图多项式的赋值，CMSOL是扩充了模计数量词的一元二阶逻辑.这个判据涵盖了文献中已知的大多数图多项式。
A graph polynomial $p(G, ar{X})$ can code numeric information about the underlying graph G in various ways: as its degree, as one of its specific coefficients or as evaluations at specific points $ar{X}= ar{x}_0$. In this paper we study the question how to prove that a given graph parameter, say *** (G ), the size of the maximal clique of G , cannot be a fixed coefficient or the evaluation at any point of the Tutte polynomial, the interlace polynomial, or any graph polynomial of some infinite family of graph polynomials.
Our result is very general. We give a sufficient condition in terms of the connection matrix of graph parameter f (G ) which implies that it cannot be the evaluation of any graph polynomial which is invariantly definable in CMSOL , the Monadic Second Order Logic augmented with modular counting quantifiers. This criterion covers most of the graph polynomials known from the literature.