Proof of a conjecture on the algebraic connectivity of a graph and its complement

2019/01/07 by Mostafa Einollahzadeh, Einollahzadeh, Mostafa, Mohammad Mahdi Karkhaneei +1 · 1 citation
Chemistry · Materials Science · Mathematics · #05C50 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Graphene research and applications #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.1901.02047

openalex publication_date 2019/01/07 · openalex created_date 2019/01/25 · openalex updated_date 2026/07/28

Abstract

For a graph G, let λ₂(G) denote its second smallest Laplacian eigenvalue. It was conjectured that λ₂(G) + λ₂(G) ≥ 1, where G is the complement of G. Here, we prove this conjecture in the general case. Also, we will show that max\λ₂(G), λ₂(G)\ ≥ 1 - O(n^{-\frac 13}), where n is the number of vertices of G.

Cited by

• A solution to Godsil's conjecture on the edge-connectivity of graphs in association schemes

Related

• A New Upper Bound for the d-dimensional Algebraic Connectivity of Arbitrary Graphs
• On the l_∞-analog of Algebraic Connectivity
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• A Lower Bound for Algebraic Connectivity based on Connection Graph Stability Method
• Some bounds on the Laplacian eigenvalues of token graphs