Homomorphisms into loop-threshold graphs

DOI10.37236/6207MaRDI QIDQ2185229zbMATHOpenAlexFDO

Authors Jonathan Cutler, Nicholas J. Kass

Publication date 4 June 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02660

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

homomorphisms into a fixed image graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Abstract: Many problems in extremal graph theory correspond to questions involving homomorphisms into a fixed image graph. Recently, there has been interest in maximizing the number of homomorphisms from graphs with a fixed number of vertices and edges into small image graphs. For the image graph $H_{extind}$, the graph on two adjacent vertices, one of which is looped, each homomorphism from $G$ to $H_{extind}$ corresponds to an independent set in $G$. It follows from the Kruskal-Katona theorem that the number of homomorphisms to $H_{extind}$ is maximized by the lex graph, whose edges form an initial segment of the lex order. A emph{loop-threshold graph} is a graph built recursively from a single vertex, which may be looped or unlooped, by successively adding either a looped dominating vertex or an unlooped isolated vertex at each stage. Thus, the graph $H_{extind}$ is a loop-threshold graph. We survey known results for maximizing the number of homomorphisms into small loop-threshold image graphs. The only extremal homomorphism problem with a loop-threshold image graph on at most three vertices not yet solved is $H_{extind}cup{E}_1$, where extremal graphs are the union of a lex graph and an empty graph. The only question that remains is the size of the lex component of the extremal graph. While we cannot give an exact answer for every number of vertices and edges, we establish the significance of and give a bound for $ell(m)$, the number of vertices in the lex component of the extremal graph with $m$ edges and at least $m+1$ vertices.

Recommendations

• Extremal graphs for homomorphisms
• Extremal graphs for homomorphisms. II
• Extremal threshold graphs for matchings and independent sets
• Extremal regular graphs: independent sets and graph homomorphisms
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree

Cites work

• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• A new method for enumerating independent sets of a fixed size in general graphs
• An entropy approach to the hard-core model on bipartite graphs
• Counting independent sets of a fixed size in graphs with a given minimum degree
• Extremal graphs for homomorphisms
• Extremal graphs for homomorphisms. II
• Extremal problems for independent set enumeration
• Extremal regular graphs: independent sets and graph homomorphisms
• Graph homomorphisms and phase transitions
• Independent sets in graphs with given minimum degree
• Maximizing \(H\)-colorings of a regular graph
• Maximizing the number of independent sets of a fixed size
• On the maximum number of cliques in a graph
• On weighted graph homomorphisms
• The maximum number of complete subgraphs in a graph with given maximum degree
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• The number of independent sets in a regular graph
• Threshold graphs and related topics
• Two problems on independent sets in graphs

Cited in

(4)

• Homomorphism-homogeneous graphs with loops
• Extremal graphs for homomorphisms. II
• Threshold graphs maximise homomorphism densities
• Extremal graphs for homomorphisms

This page was built for publication: Homomorphisms into loop-threshold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185229)