Maximizing algebraic connectivity for certain families of graphs

2014/12/17 by T. Kolokolnikov, Théodore Kolokolnikov, Kolokolnikov, Theodore · 3 citations
Mathematics · Computer Science · #Graph theory and applications #Interconnection Networks and Systems #Advanced Graph Theory Research

paper · doi:10.1016/j.laa.2014.12.023

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.

Citations

• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays

Cited by

• Cubic bipartite graphs with minimum spectral gap
• The non-existence of some Moore polygons and spectral Moore bounds
• Algebraic connectivity in normed spaces