Polynomial graph invariants from homomorphism numbers

详细信息    查看全文

• 作者：Delia Garijo^a ; ^{dgarijo@us.es" class="auth_mail" title="E-mail the corresponding author} ; Andrew Goodall^b ; ^{andrew@iuuk.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author} ; Jaroslav Ne&scaron ; etřil^b ; ^{nesetril@kam.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph polynomial ; Graph homomorphism ; Graph sequence
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1315-1328
• 全文大小：684 K

文摘

We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences $\left(H_k\right)$ indexed by a tuple $k=(k_1,\dots ,k_h)$ of positive integers, with the property that, for each fixed graph G$G$, there is a multivariate polynomial p(G;x₁,…,x_h)$p(G;x_1,\dots ,x_h)$ such that the number of homomorphisms from G$G$ to $H_k$ is given by the evaluation p(G;k₁,…,k_h)$p(G;k_1,\dots ,k_h)$. A classical example is the sequence of complete graphs (K_k)$\left(K_k\right)$, for which p(G;x)$p(G;x)$ is the chromatic polynomial of G$G$. Our construction is based on tree model representations of graphs. It produces a large family of graph polynomials which includes the Tutte polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial. We also introduce a new graph parameter, the branching core size of a simple graph, derived from its representation under a particular tree model, and related to how many involutive automorphisms it has. We prove that a countable family of graphs of bounded branching core size is always contained in the union of a finite number of strongly polynomial sequences.