Premium
Extremal graphs for homomorphisms
Author(s) -
Cutler Jonathan,
Radcliffe A. J.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20530
Subject(s) - homomorphism , mathematics , combinatorics , graph homomorphism , extremal graph theory , discrete mathematics , vertex (graph theory) , graph , line graph , voltage graph
The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H . We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K 2 with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P ∘ 2 , the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011