Graph operations and upper bounds on graph homomorphism counts
Graph operations and upper bounds on graph homomorphism counts
复制标题
图运算和图同态计数的上限
作者：
Luke Sernau
Galvin [5]的一个猜想：对任意n-顶点d-正则图G和任意图H（可能有圈），hom（G，H）≤max{hom（Kd，d，H）n2 d，hom（Kd+1，H）nd+1}，其中hom（G，H）是G到H的同态数.通过利用图张量积和图幂的性质，我们还找到了新的H的无限族，对于所有n-顶点，d-正则G，hom（G，H）上的上述界成立。特别是，我们证明，如果HWR是三个顶点上的完整循环路径，也称为Widom-Rowlinson图，那么对于所有n-顶点、d-正则G，hom（G，H WR）≤hom（Kd+1，H WR）nd+1。这验证了Galvin的一个猜想。
We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any n‐vertex, d‐regular graph G and any graph H (possibly with loops), hom(G,H)≤max{hom(Kd,d,H)n2d,hom(Kd+1,H)nd+1},where hom(G,H) is the number of homomorphisms from G to H. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of H for which the bound stated above on hom(G,H) holds for all n‐vertex, d‐regular G. In particular, we show that if HWR is the complete looped path on three vertices, also known as the Widom–Rowlinson graph, then hom(G,H WR )≤hom(Kd+1,H WR )nd+1for all n‐vertex, d‐regular G. This verifies a conjecture of Galvin.