Maximizing algebraic connectivity for certain families of graphs

2014/12/17 by Kolokolnikov, Theodore · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1412.6147

Abstract

We investigate the bounds on algebraic connectivity of graphs subject to constraints on the number of edges, vertices, and topology. We show that the algebraic connectivity for any tree on n vertices and with maximum degree d is bounded above by 2(d-2) (1)/(n)+O(\fracln nn²) . We then investigate upper bounds on algebraic connectivity for cubic graphs. We show that algebraic connectivity of a cubic graph of girth g is bounded above by 3-2^3/2cos(π/\lfloor g/2\rfloor) , which is an improvement over the bound found by Nilli [A. Nilli, Electron. J. Combin., 11(9), 2004]. Finally, we propose several conjectures and open questions.

Cited by

• The non-existence of some Moore polygons and spectral Moore bounds
• Algebraic connectivity in normed spaces

Related

• A lower bound for the algebraic connectivity of a graph in terms of the domination number
• Algebraic connectivity of connected graphs with fixed number of pendant vertices
• Attainable bounds for algebraic connectivity and maximally-connected regular graphs
• A note on algebraic connectivity of 2-connected graphs
• A New Upper Bound for the d-dimensional Algebraic Connectivity of Arbitrary Graphs