The planar graph algebraic-connectivity conjecture

About 25 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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.