Homomorphisms into loop-threshold graphs

DOI10.37236/6207zbMATH Open1441.05120arXiv1606.02660OpenAlexW3030445364MaRDI QIDQ2185229FDOQ2185229

Authors: Jonathan Cutler, Nicholas J. Kass 

Publication date: 4 June 2020

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

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.

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

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

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

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)

Cites Work

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

Cited In (3)

• Extremal graphs for homomorphisms. II
• Homomorphism-homogeneous graphs with loops
• 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)