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

(45)

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

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)