On the Fiedler value of large planar graphs

Abstract

The Fiedler value ${\lambda }_2$, also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs $G$ with $n$ vertices, denoted by ${\lambda }_{2\max }$, and we show the bounds $2+\Theta (\frac{1}{n^2})\le {\lambda }_{2\max }\le 2+O(\frac{1}{n})$. We also provide bounds on the maximum Fiedler value for the following classes of planar graphs: Bipartite planar graphs, bipartite planar graphs with minimum vertex degree~3, and outerplanar graphs. Furthermore, we derive almost tight bounds on ${\lambda }_{2\max }$ for two more classes of graphs, those of bounded genus and $K_h$-minor-free graphs.

21 pages, 4 figures, 1 table. Version accepted in Linear Algebra and Its Applications