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

Original language | English |
---|---|

Pages (from-to) | 261-284 |

Number of pages | 24 |

Journal | Journal of Graph Theory |

Volume | 67 |

Issue number | 4 |

DOIs | |

State | Published - 1 Aug 2011 |

### Fingerprint

### Keywords

- extremal problem
- homomorphisms
- threshold graphs

### Cite this

*Journal of Graph Theory*,

*67*(4), 261-284. https://doi.org/10.1002/jgt.20530

}

*Journal of Graph Theory*, vol. 67, no. 4, pp. 261-284. https://doi.org/10.1002/jgt.20530

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

Research output: Contribution to journal › Article › Research › peer-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 -