Spectral bounds for the connectivity of regular graphs with given order

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

doi:10.13001/1081-3810.3675

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 journal › Article › Academic › peer-review

14 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 language	English
Article number	33
Pages (from-to)	428-443
Number of pages	16
Journal	Electronic Journal of Linear Algebra
Volume	34
DOIs	https://doi.org/10.13001/1081-3810.3675
Publication status	Published - Sept 2018
Externally published	Yes

Funding

†Department of Quantitative Economics, Maastricht University, Maastricht, The Netherlands; Department of Pure Mathematics and Computer Algebra, Ghent University, Ghent, Belgium ([email protected]). Research partially supported by The Combinatorics Foundation and NSF-DMS Grants 1604458, 1604773, 1604697 and 1603823. ‡Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA ([email protected]). Research partially supported by NSF Grant 1450681 and NSF-DMS Grants 1604458, 1604773, 1604697 and 1603823. §Department of Mathematics, Iowa State University, Ames, IA 50011, USA ([email protected]). Research partially supported by Institute of Mathematics and its Applications and NSF-DMS Grants 1604458, 1604773, 1604697 and 1603823. ¶Applied Mathematics and Statistics, The State University of New York Korea, Incheon, 21985, Republic of Korea ([email protected]). Research partially supported by The Combinatorics Foundation, NSF-DMS Grants 1604458, 1604773, 1604697 and 1603823, and NRF-2017R1D1A1B03031758. ‖Department of Mathematics, University of Central Florida, Orlando, FL 32816, USA ([email protected]). Research partially supported by NSF-DMS Grants 1604458, 1604773, 1604697 and 1603823.

Keywords

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

Access to Document

10.13001/1081-3810.3675

Cite this

@article{bf049143eaae4c2b9f50bc51ef84692d,

title = "Spectral bounds for the connectivity of regular graphs with given order",

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.",

keywords = "Algebraic connectivity, Edge-connectivity, Regular multigraph, Second-largest eigenvalue, Vertex-connectivity",

author = "Aida Abiad and Boris Brimkov and Xavier Mart{\'i}nez-Rivera and O. Suil and Jingmei Zhang",

year = "2018",

month = sep,

doi = "10.13001/1081-3810.3675",

language = "English",

volume = "34",

pages = "428--443",

journal = "Electronic Journal of Linear Algebra",

issn = "1537-9582",

publisher = "International Linear Algebra Society",

}

TY - JOUR

T1 - Spectral bounds for the connectivity of regular graphs with given order

AU - Abiad, Aida

AU - Brimkov, Boris

AU - Martínez-Rivera, Xavier

AU - Suil, O.

AU - Zhang, Jingmei

PY - 2018/9

Y1 - 2018/9

N2 - 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.

AB - 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.

KW - Algebraic connectivity

KW - Edge-connectivity

KW - Regular multigraph

KW - Second-largest eigenvalue

KW - Vertex-connectivity

UR - http://www.scopus.com/inward/record.url?scp=85055340847&partnerID=8YFLogxK

U2 - 10.13001/1081-3810.3675

DO - 10.13001/1081-3810.3675

M3 - Article

AN - SCOPUS:85055340847

SN - 1537-9582

VL - 34

SP - 428

EP - 443

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

M1 - 33

ER -

Spectral bounds for the connectivity of regular graphs with given order

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this