Homomorphisms into loop-threshold graphs

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

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

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_{e x t i n d}

, the graph on two adjacent vertices, one of which is looped, each homomorphism from

G

to

H_{e x t i n d}

corresponds to an independent set in

G

. It follows from the Kruskal-Katona theorem that the number of homomorphisms to

H_{e x t i n d}

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_{e x t i n d}

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_{e x t i n d} c u p 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

e l l (m)

, the number of vertices in the lex component of the extremal graph with

m

edges and at least

m + 1

vertices.

Review text

Summary: 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_{\text{ind}} \), the graph on two adjacent vertices, one of which is looped, each homomorphism from \(G\) to \(H_{\text{ind}}\) corresponds to an independent set in \(G\). It follows from the Kruskal-Katona theorem that the number of homomorphisms to \(H_{\text{ind}}\) is maximized by the lex graph, whose edges form an initial segment of the lex order. A 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_{\text{ind}}\) 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_{\text{ind}}\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 bounds on \(\ell(m)\), the number of vertices in the lex component of the extremal graph with \(m\) edges and at least \(m+1\) vertices.

Recommendations

Cites work

Cited in

(4)

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)