On weighted graph homomorphisms

zbMATH Open1061.05068arXiv1206.3160MaRDI QIDQ4660722FDOQ4660722

Authors: David Galvin, Prasad Tetali 

Publication date: 4 April 2005

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.

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

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

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)

Cited In (43)

• Counting proper colourings in 4-regular graphs via the Potts model
• Homomorphisms from the torus
• A proof of Tomescu's graph coloring conjecture
• The number of independent sets in an irregular graph
• 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
• Counting dominating sets and related structures in graphs
• Topological aspects of weighted graphs with application to fixed point theory
• On the Widom-Rowlinson occupancy fraction in regular graphs
• \(H\)-colouring bipartite graphs
• The bipartite swapping trick on graph homomorphisms
• Counting colorings of a regular graph
• On weighted adjacency operators associated to directed graphs
• \(H\)-coloring tori
• Minimizing the number of independent sets in triangle-free regular graphs
• Extremal colorings and independent sets
• Title not available (Why is that?)
• Two equivalent measures on weighted hypergraphs
• 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
• Tight bounds on the coefficients of partition functions via stability
• On vertex-weighted graph realizations
• A reverse Sidorenko inequality
• Homomorphisms into loop-threshold graphs
• Rigidity of proper colorings of \(\mathbb{Z}^d \)
• Interview with Yufei Zhao
• Notes on use of generalized entropies in counting
• An upper bound for the number of independent sets in regular graphs
• Maximizing the number of independent sets in claw-free cubic graphs
• Title not available (Why is that?)
• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• The weighted complexity and the determinant functions of graphs
• Counting independent sets in cubic graphs of given girth
• Extremal regular graphs: independent sets and graph homomorphisms

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)