On the maximum spread of planar and outerplanar graphs

arXiv2209.13776MaRDI QIDQ6412166FDOQ6412166

Zelong Li, William Linz, Linyuan Lu, Zhiyu Wang

Publication date: 27 September 2022

Abstract: The spread of a graph $G$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $G$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $n$, the $n$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $lceil(2n-1)/3ceil$ vertices and $lfloor(n-2)/3floor$ isolated vertices. For planar graphs, we show that the extremal $n$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $lceil(2n-2)/3ceil$ vertices and $lfloor(n-4)/3floor$ isolated vertices.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Planar graphs; geometric and topological aspects of graph theory (05C10)

This page was built for publication: On the maximum spread of planar and outerplanar graphs

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