2016/03/12 by O Suil, O, Suil
Chemistry · Materials Science · Mathematics · #05C40 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Nanocluster Synthesis and Applications #Synthesis and Properties of Aromatic Compounds
paper · pdf · doi:10.48550/arxiv.1603.03960
openalex publication_date 2016/03/12 · openalex created_date 2016/10/21 · openalex updated_date 2026/07/28
Let μ2(G) be the second smallest Laplacian eigenvalue of a graph G. The vertex connectivity of G, written κ(G), is the minimum size of a vertex set S such that G-S is disconnected. Fiedler proved that μ2(G) ≤ κ(G) for a non-complete simple graph G; for this reason μ2(G) is called the "algebraic connectivity" of G. We extend his result to multigraphs. For a pair of vertices u and v, let m(u,v) be the number of edges with endpoints u and v. For a vertex v, let m(v)=maxu ∈ N(v) m(v,u), where N(v) is the set of neighbors of v, and let m(G)=maxv ∈ V(G) m(v). We prove that for any multigraph G whose underlying graph is not a complete graph, μ2(G) ≤ κ(G) m(G). We also prove that for any d-regular multigraph G whose underlying graph is not the complete graph with 2 vertices, if μ2(G) > \frac d4, then G is 2-connected. For t≥2 and infinitely many d, we construct d-regular multigraphs H with μ2(H)=d, κ(H)=t, and m(H)=\frac dt. These graphs show that the inequality μ2(G) ≤ κ(G) m(G) is sharp. In addition, we prove that if G is a d-regular multigraph whose underlying graph is not a complete graph, then μ2(G) ≤ d; equality holds for the graphs in the construction.