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 ρ(G)≥ρ(Fn), where Fn 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=Fn. 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 Fn, 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 F15. Since ρ(Fn)<4 for all n, this completes the proof. The numerical inequalities used along the way are certified by explicit integer vectors with small entries.
Related
- Size and spectral radius conditions for the existence of k-factor in graphs with given minimum degree
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- The maximum spectral radius of outerplanar and planar k-uniform hypergraphs
- Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair
- On the fault-tolerant metric dimension of maximal outerplanar graphs
BibTeX
@misc{suil2026minimum,
title = {{The minimum spectral radius of maximal outerplanar graphs}},
author = {Suil O},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33333},
eprint = {2609.33333},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33333},
}
RIS
TY - UNPB
TI - The minimum spectral radius of maximal outerplanar graphs
AU - Suil O
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33333
UR - https://arxiv.org/abs/2609.33333
AB - 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 ρ(G)≥ρ(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 ρ(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.
ER -