On weighted graph homomorphisms

MaRDI QIDQ4660722zbMATH OpenFDO

Authors David Galvin, Prasad Tetali

Publication date 4 April 2005

Full work available at URL https://arxiv.org/abs/1206.3160

zbMATH Keywords

entropygraph homomorphismindependence set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For given graphs $G$ and $H$, let $|Hom(G,H)|$ denote the set of graph homomorphisms from $G$ to $H$. We show that for any finite, $n$-regular, bipartite graph $G$ and any finite graph $H$ (perhaps with loops), $|Hom(G,H)|$ is maximum when $G$ is a disjoint union of $K_{n,n}$'s. This generalizes a result of J. Kahn on the number of independent sets in a regular bipartite graph. We also give the asymptotics of the logarithm of $|Hom(G,H)|$ in terms of a simply expressed parameter of $H$. We also consider weighted versions of these results which may be viewed as statements about the partition functions of certain models of physical systems with hard constraints.

Recommendations

• Weighted graph homomorphisms and the Tutte polynomial
• scientific article; zbMATH DE number 10422
• On Gregus-Ćirić mappings on weighted graphs
• scientific article; zbMATH DE number 3983195
• scientific article; zbMATH DE number 12050
• scientific article; zbMATH DE number 3287786
• On the enumeration of certain weighted graphs
• On vertex-weighted graph realizations
• On weighted modulo orientation of graphs
• On weighted directed graphs

Cited in

(43)

• Extremal regular graphs: independent sets and graph homomorphisms
• Counting proper colourings in 4-regular graphs via the Potts model
• A proof of Tomescu's graph coloring conjecture
• Homomorphisms from the torus
• Matchings and independent sets of a fixed size in regular graphs
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• The number of independent sets in an irregular graph
• Counting dominating sets and related structures in graphs
• Topological aspects of weighted graphs with application to fixed point theory
• \(H\)-colouring bipartite graphs
• On the Widom-Rowlinson occupancy fraction in regular graphs
• The bipartite swapping trick on graph homomorphisms
• Counting colorings of a regular graph
• H-coloring tori
• On weighted adjacency operators associated to directed graphs
• Minimizing the number of independent sets in triangle-free regular graphs
• Extremal colorings and independent sets
• Two equivalent measures on weighted hypergraphs
• scientific article; zbMATH DE number 1525222 (Why is no real title available?)
• Graph-approximations of multivalued weighted maps
• Tomescu's Graph Coloring Conjecture for $\ell$-Connected Graphs
• A proof of the upper matching conjecture for large graphs
• Recognizing weighted directed cartesian graph bundles
• Rigidity of 3-colorings of the discrete torus
• Extremal problems for independent set enumeration
• The homomorphism domination exponent
• On the number of independent sets in uniform, regular, linear hypergraphs
• Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree
• On Sidorenko's conjecture for determinants and Gaussian Markov random fields
• Maximizing the number of \(H\)-colorings of graphs with a fixed minimum degree
• A reverse Sidorenko inequality
• On vertex-weighted graph realizations
• Tight bounds on the coefficients of partition functions via stability
• Homomorphisms into loop-threshold graphs
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Notes on use of generalized entropies in counting
• Interview with Yufei Zhao
• An upper bound for the number of independent sets in regular graphs
• Maximizing the number of independent sets in claw-free cubic graphs
• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• scientific article; zbMATH DE number 10422 (Why is no real title available?)
• The weighted complexity and the determinant functions of graphs
• Counting independent sets in cubic graphs of given girth

This page was built for publication: On weighted graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4660722)