Back to Search
Start Over
On the maximum spread of planar and outerplanar graphs
- Publication Year :
- 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)/3\rceil$ vertices and $\lfloor(n-2)/3\rfloor$ 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)/3\rceil$ vertices and $\lfloor(n-4)/3\rfloor$ isolated vertices.
- Subjects :
- Mathematics - Combinatorics
05C10, 05C50
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2209.13776
- Document Type :
- Working Paper