An upper bound on the algebraic connectivity of regular graphs

2015/03/05 by Sera Aylin Cakiroglu, Cakiroglu, Sera Aylin
Computer Science · Materials Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Graphene research and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1503.01758

openalex publication_date 2015/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive a new upper bound on the algebraic connectivity of a regular graph using the Higman-Sims technique. Together with a new result on the connectivity of the neighbourhood graph of strongly regular graphs, our result gives a characterization of a class of strongly regular graphs that maximize the algebraic connectivity amongst regular graphs.

Related

• Attainable bounds for algebraic connectivity and maximally-connected regular graphs
• A lower bound for the algebraic connectivity of a graph in terms of the domination number
• A New Upper Bound for the d-dimensional Algebraic Connectivity of Arbitrary Graphs
• The Algebraic Connectivity and the Clique Number of Graphs
• On the d-dimensional algebraic connectivity of graphs