The planar graph algebraic-connectivity conjecture
Let be a planar graph, and let denote its algebraic connectivity, the second-smallest eigenvalue of its Laplacian. The graphs and are the complete graph on four vertices and the join of two isolated vertices with a four-cycle, respectively. Planar algebraic-connectivity conjecture.
with equality if and only if or . If is neither of these graphs, then .
The conjecture would determine the maximum algebraic connectivity of planar graphs and its equality cases; the source reports that it has not been proved.
References
Primary source
Pedro Freitas, “A Heawood-type result for the algebraic connectivity of graphs on surfaces”, arXiv:math/0109191 (2001).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.