✦ LIBER ✦

Extremal graphs for homomorphisms

✍ Scribed by Jonathan Cutler; A. J. Radcliffe

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 219 KB
Volume: 67
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20530

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Independence and graph homomorphisms gra

Independence and graph homomorphisms graph homomorphisms

✍ Michael O. Albertson; Lily Chan; Ruth Haas 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract A graph with __n__ vertices that contains no triangle and no 5‐cycle and minimum degree exceeding __n__/4 contains an independent set with at least (3__n__)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism

Extremal Graphs for Intersecting Triangl

Extremal Graphs for Intersecting Triangles

✍ P. Erdos; Z. Furedi; R.J. Gould; D.S. Gunderson 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 400 KB

It is known that for a graph on $n$ vertices $\left\lfloor n^{2} / 4\right\rfloor+1$ edges is sufficient for the existence of many triangles. In this paper, we determine the minimum number of edges sufficient for the existence of $k$ triangles intersecting in exactly one common vertex. C 1995

Homomorphism–homogeneous graphs

✍ Momchil Rusinov; Pascal Schweitzer 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

## Abstract We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Homomorphism bounds for oriented planar

Homomorphism bounds for oriented planar graphs

✍ T. H. Marshall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract If ${\cal C}$ is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a __homomorphism bound__ for ${\cal C}$ if there is a homomorphism from each graph in ${\cal C}$ to __H__. We find some necessary conditions for a graph to be a homomorphism bo

Extremal interval graphs

✍ Jürgen Eckhoff 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB

## Abstract An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for t