On weighted graph homomorphisms (Q4660722)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2151252
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On weighted graph homomorphisms |
scientific article; zbMATH DE number 2151252 |
Statements
4 April 2005
0 references
graph homomorphism
0 references
independence set
0 references
entropy
0 references
0.94125175
0 references
0.91650957
0 references
0.9064143
0 references
0 references
0.90349436
0 references
0 references
A result of \textit{J. Khan} [Comb. Probab. Comput. 10, 219--237 (2001; Zbl 0985.60088)] gives a bound for the number of independence sets in regular bipartite graphs. This paper generalizes this result by considering the set of graph homomorphisms. In particular, the authors show that the set of graph homomorphisms from a finite, bipartite graph \(G\) to any finite graph \(H\) is maximized when \(G\) is a disjoint union of complete bipartite graphs. More general weighted versions of the result are also given. The method of proof extends Kahn's entropy approach [{op. cit.}]. For the entire collection see [Zbl 1051.05003].
0 references
