The maximum-spread outerplanar graph conjecture

Let PkP_k denote the path on kk vertices, let K1K_1 denote the one-vertex graph, and let GHG\vee H denote the join of graphs GG and HH. The spread of a graph is the difference between the largest and most negative eigenvalue of its adjacency matrix. An outerplanar graph is a graph that can be drawn in the plane without crossings with every vertex incident with the unbounded face.

Maximum-spread outerplanar graph conjecture. For nn sufficiently large, the unique nn-vertex outerplanar graph of maximum spread is

K1Pn1.K_1\vee P_{n-1}.

The paper's main theorem shows that every sufficiently large extremal outerplanar graph has the form K1FK_1\vee F, where FF is a linear forest with Ω(n)\Omega(n) edges. The conjecture identifies the remaining forest as the path Pn1P_{n-1} and asserts uniqueness; the source leaves this determination open.

Sources & referencesView supporting material

Primary source

Daniel Gotshall, Megan O'Brien and Michael Tait, “On the spread of outerplanar graphs”, arXiv:2111.11820 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.