The planar graph algebraic-connectivity conjecture

From papers

Let GG be a planar graph, and let a(G)a(G) denote its algebraic connectivity, the second-smallest eigenvalue of its Laplacian. The graphs K4K_4 and 2K1+˙C42K_1\dot{+}C_4 are the complete graph on four vertices and the join of two isolated vertices with a four-cycle, respectively. Planar algebraic-connectivity conjecture.

a(G)4,a(G)\leq 4,

with equality if and only if G=K4G=K_4 or G=2K1+˙C4G=2K_1\dot{+}C_4. If GG is neither of these graphs, then a(G)3a(G)\leq 3.

The conjecture would determine the maximum algebraic connectivity of planar graphs and its equality cases; the source reports that it has not been proved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pedro Freitas, “A Heawood-type result for the algebraic connectivity of graphs on surfaces”, arXiv:math/0109191 (2001).

Solutions 0

No solutions have been posted yet.