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 class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si30.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=642ccf987e4557b9af7de152dc695fc6">class="imgLazyJSB inlineImage" height="15" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si30.gif">class="mathContainer hidden">class="mathCode">$\left(H_k\right)$ indexed by a tuple class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si31.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=6458135dc12b7a12a2a4bcdc9e9740a0">class="imgLazyJSB inlineImage" height="15" width="111" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si31.gif">class="mathContainer hidden">class="mathCode">$k=(k_1,\dots ,k_h)$ of positive integers, with the property that, for each fixed graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, there is a multivariate polynomial class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si33.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=6290544a306f025a73c904e36ade38aa" title="Click to view the MathML source">p(G;x₁,…,x_h)class="mathContainer hidden">class="mathCode">$p(G;x_1,\dots ,x_h)$ such that the number of homomorphisms from class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ to class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si35.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=c97d4a78221ac749506292d6b4ff598e">class="imgLazyJSB inlineImage" height="14" width="19" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si35.gif">class="mathContainer hidden">class="mathCode">$H_k$ is given by the evaluation class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si36.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=bfc2ff576eb0a3004207cfba72696d78" title="Click to view the MathML source">p(G;k₁,…,k_h)class="mathContainer hidden">class="mathCode">$p(G;k_1,\dots ,k_h)$. A classical example is the sequence of complete graphs class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si37.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=8826bdc5dfac4d7fb6b79e808f8d9c5f" title="Click to view the MathML source">(K_k)class="mathContainer hidden">class="mathCode">$\left(K_k\right)$, for which class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si38.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=070bede4394a8f58902ee12c0f565062" title="Click to view the MathML source">p(G;x)class="mathContainer hidden">class="mathCode">$p(G;x)$ is the chromatic polynomial of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$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.