### 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 language | English |
---|---|

Pages (from-to) | 42-59 |

Number of pages | 18 |

Journal | Journal of Graph Theory |

Volume | 76 |

Issue number | 1 |

DOIs | |

State | Published - 1 May 2014 |

### Fingerprint

### Keywords

- extremal problem
- graph homomorphisms

### Cite this

*Journal of Graph Theory*,

*76*(1), 42-59. https://doi.org/10.1002/jgt.21749

}

*Journal of Graph Theory*, vol. 76, no. 1, pp. 42-59. https://doi.org/10.1002/jgt.21749

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

Research output: Contribution to journal › Article

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

AN - SCOPUS:84897610625

VL - 76

SP - 42

EP - 59

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -