Spectral bounds for the connectivity of regular graphs with given order

Aida Abiad, Boris Brimkov, Xavier Martínez-Rivera, O. Suil, Jingmei Zhang

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex-and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, two upper bounds are presented for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex-or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar.

Original languageEnglish
Article number33
Pages (from-to)428-443
Number of pages16
JournalElectronic Journal of Linear Algebra
Volume34
DOIs
Publication statusPublished - Sep 2018
Externally publishedYes

Keywords

  • Algebraic connectivity
  • Edge-connectivity
  • Regular multigraph
  • Second-largest eigenvalue
  • Vertex-connectivity

Fingerprint

Dive into the research topics of 'Spectral bounds for the connectivity of regular graphs with given order'. Together they form a unique fingerprint.

Cite this