Extremal graphs for homomorphisms

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

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 K2 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.

Original languageEnglish
Pages (from-to)261-284
Number of pages24
JournalJournal of Graph Theory
Volume67
Issue number4
DOIs
StatePublished - Aug 2011

Keywords

  • extremal problem
  • homomorphisms
  • threshold graphs

Fingerprint

Dive into the research topics of 'Extremal graphs for homomorphisms'. Together they form a unique fingerprint.

Cite this