New conjectures on algebraic connectivity and the Laplacian spread of graphs

2022/01/01 by Wayne Barrett, Emily Evans, Barrett, Wayne +5
Materials Science · Mathematics · Physics and Astronomy · #05C50 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Graphene research and applications #math.CO #msc:05C50

paper · pdf · doi:10.48550/arxiv.2201.04225

openalex publication_date 2022/01/01 · arxiv created 2022/01/11 · arxiv updated 2022/01/13 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/30

Abstract

We conjecture a new lower bound on the algebraic connectivity of a graph that involves the number of vertices of high eccentricity in a graph. We prove that this lower bound implies a strengthening of the Laplacian Spread Conjecture. We discuss further conjectures, also strengthening the Laplacian Spread Conjecture, that include a conjecture for simple graphs and a conjecture for weighted graphs.

Related

• Attainable bounds for algebraic connectivity and maximally-connected regular graphs
• Proof of a conjecture on the algebraic connectivity of a graph and its complement
• A lower bound for the algebraic connectivity of a graph in terms of the domination number
• On the l_∞-analog of Algebraic Connectivity
• On the Laplacian spread of digraphs