Extremal graphs for homomorphisms II

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

Extremal problems for graph homomorphisms have recently become a topic of much research. Let hom(G,H) denote the number of homomorphisms from G to H. A natural set of problems arises when we fix an image graph H and determine which graph(s) G on n vertices and m edges maximize hom(G,H). We prove that if H is loop-threshold, then, for every n and m, there is a threshold graph G with n vertices and m edges that maximizes hom(G,H). Similarly, we show that loop-quasi-threshold image graphs have quasi-threshold extremal graphs. In the case H=P3o, the path on three vertices in which every vertex in looped, the authors [5] determined a set of five graphs, one of which must be extremal for hom(G,P3o). Also in this article, using similar techniques, we determine a set of extremal graphs for "the fox," a graph formed by deleting the loop on one of the end-vertices of P3o. The fox is the unique connected loop-threshold image graph on at most three vertices for which the extremal problem was not previously solved.

Original languageEnglish
Pages (from-to)42-59
Number of pages18
JournalJournal of Graph Theory
Volume76
Issue number1
DOIs
StatePublished - 1 May 2014

Fingerprint

Extremal Graphs
Homomorphisms
Graph in graph theory
Threshold Graph
Extremal Problems
Maximise
Graph Homomorphisms
Denote
Path
Vertex of a graph

Keywords

  • extremal problem
  • graph homomorphisms

Cite this

Cutler, Jonathan ; Radcliffe, A. J. / Extremal graphs for homomorphisms II. In: Journal of Graph Theory. 2014 ; Vol. 76, No. 1. pp. 42-59.
@article{4632cd132e374299a65ade6943a248d2,
title = "Extremal graphs for homomorphisms II",
abstract = "Extremal problems for graph homomorphisms have recently become a topic of much research. Let hom(G,H) denote the number of homomorphisms from G to H. A natural set of problems arises when we fix an image graph H and determine which graph(s) G on n vertices and m edges maximize hom(G,H). We prove that if H is loop-threshold, then, for every n and m, there is a threshold graph G with n vertices and m edges that maximizes hom(G,H). Similarly, we show that loop-quasi-threshold image graphs have quasi-threshold extremal graphs. In the case H=P3o, the path on three vertices in which every vertex in looped, the authors [5] determined a set of five graphs, one of which must be extremal for hom(G,P3o). Also in this article, using similar techniques, we determine a set of extremal graphs for {"}the fox,{"} a graph formed by deleting the loop on one of the end-vertices of P3o. The fox is the unique connected loop-threshold image graph on at most three vertices for which the extremal problem was not previously solved.",
keywords = "extremal problem, graph homomorphisms",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2014",
month = "5",
day = "1",
doi = "10.1002/jgt.21749",
language = "English",
volume = "76",
pages = "42--59",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "1",

}

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

In: Journal of Graph Theory, Vol. 76, No. 1, 01.05.2014, p. 42-59.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Extremal graphs for homomorphisms II

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2014/5/1

Y1 - 2014/5/1

N2 - Extremal problems for graph homomorphisms have recently become a topic of much research. Let hom(G,H) denote the number of homomorphisms from G to H. A natural set of problems arises when we fix an image graph H and determine which graph(s) G on n vertices and m edges maximize hom(G,H). We prove that if H is loop-threshold, then, for every n and m, there is a threshold graph G with n vertices and m edges that maximizes hom(G,H). Similarly, we show that loop-quasi-threshold image graphs have quasi-threshold extremal graphs. In the case H=P3o, the path on three vertices in which every vertex in looped, the authors [5] determined a set of five graphs, one of which must be extremal for hom(G,P3o). Also in this article, using similar techniques, we determine a set of extremal graphs for "the fox," a graph formed by deleting the loop on one of the end-vertices of P3o. The fox is the unique connected loop-threshold image graph on at most three vertices for which the extremal problem was not previously solved.

AB - Extremal problems for graph homomorphisms have recently become a topic of much research. Let hom(G,H) denote the number of homomorphisms from G to H. A natural set of problems arises when we fix an image graph H and determine which graph(s) G on n vertices and m edges maximize hom(G,H). We prove that if H is loop-threshold, then, for every n and m, there is a threshold graph G with n vertices and m edges that maximizes hom(G,H). Similarly, we show that loop-quasi-threshold image graphs have quasi-threshold extremal graphs. In the case H=P3o, the path on three vertices in which every vertex in looped, the authors [5] determined a set of five graphs, one of which must be extremal for hom(G,P3o). Also in this article, using similar techniques, we determine a set of extremal graphs for "the fox," a graph formed by deleting the loop on one of the end-vertices of P3o. The fox is the unique connected loop-threshold image graph on at most three vertices for which the extremal problem was not previously solved.

KW - extremal problem

KW - graph homomorphisms

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

U2 - 10.1002/jgt.21749

DO - 10.1002/jgt.21749

M3 - Article

VL - 76

SP - 42

EP - 59

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -