
doi: 10.1002/jgt.21749
AbstractExtremal problems for graph homomorphisms have recently become a topic of much research. Let 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 . 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 . Similarly, we show that loop‐quasi‐threshold image graphs have quasi‐threshold extremal graphs. In the case , 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 . 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 . The fox is the unique connected loop‐threshold image graph on at most three vertices for which the extremal problem was not previously solved.
Extremal problems in graph theory, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), graph homomorphisms, extremal problem
Extremal problems in graph theory, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), graph homomorphisms, extremal problem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
