A note on Fiedler value of classes with sublinear separators

Abstrakt

The n-th Fiedler value of a class of graphs C is the maximum second eigenvalue lambda(2)(G) of a graph G is an element of C with n vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the n-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

Klíčová slova

• Graph
• Fiedler value
• Vertex separators
• Shallow minor
• Sparsity