Extremal graphs for homomorphisms

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

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 - 1 Aug 2011

Fingerprint

Extremal Graphs
Homomorphisms
Threshold Graph
Graph in graph theory
Graph Homomorphisms
Extremal Problems
Statistical Physics
Independent Set
Graph theory
Counting
Upper bound
Path
Vertex of a graph

Keywords

  • extremal problem
  • homomorphisms
  • threshold graphs

Cite this

Cutler, Jonathan ; Radcliffe, A. J. / Extremal graphs for homomorphisms. In: Journal of Graph Theory. 2011 ; Vol. 67, No. 4. pp. 261-284.
@article{db71255d17cc4cb4861bcd4352b5a733,
title = "Extremal graphs for homomorphisms",
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.",
keywords = "extremal problem, homomorphisms, threshold graphs",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2011",
month = "8",
day = "1",
doi = "10.1002/jgt.20530",
language = "English",
volume = "67",
pages = "261--284",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "4",

}

Extremal graphs for homomorphisms. / Cutler, Jonathan; Radcliffe, A. J.

In: Journal of Graph Theory, Vol. 67, No. 4, 01.08.2011, p. 261-284.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Extremal graphs for homomorphisms

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2011/8/1

Y1 - 2011/8/1

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

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

KW - extremal problem

KW - homomorphisms

KW - threshold graphs

UR - http://www.scopus.com/inward/record.url?scp=79959752640&partnerID=8YFLogxK

U2 - 10.1002/jgt.20530

DO - 10.1002/jgt.20530

M3 - Article

VL - 67

SP - 261

EP - 284

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 4

ER -