The minimum spectral radius of maximal outerplanar graphs

Abstract

An outerplanar graph is \emph{maximal} if no edge can be added without losing outerplanarity. Lin and Ning determined the outerplanar graph with the largest spectral radius, and the maximizer is a maximal outerplanar graph. We determine the minimizer. In this paper, we prove that every $n$-vertex maximal outerplanar graph $G$ satisfies $\rho(G)\ge\rho(F_n)$, where $F_n$ is the zig-zag triangulation of the $n$-gon, that is, the square of the path on $n$ vertices, with equality if and only if $G=F_n$. The proof uses three local operations on maximal outerplanar graphs, each of which strictly decreases the spectral radius: the first reverses the way a piece is attached along a chord, and the second and third move a piece from one vertex to its twin across a chord when the twin carries nothing or a single ear, respectively. A graph at which no operation applies is $F_n$, or has spectral radius greater than $4$, or consists of a central triangle with three zig-zag blades of at least three triangles each and has at most $15$ vertices; in the last case it contains one of two explicit graphs on $12$ vertices whose spectral radius exceeds that of $F_{15}$. Since $\rho(F_n)<4$ for all $n$, this completes the proof. The numerical inequalities used along the way are certified by explicit integer vectors with small entries.