On the maximum spread of planar and outerplanar graphs

MaRDI QIDQ6412166zbMATH OpenFDO

Authors Zelong Li, William Linz, Linyuan Lu, Zhiyu Wang

Publication date 27 September 2022

Mathematics Subject Classification ID

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

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.

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)