Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Czechoslovak Mathematical Journal

Sebastian M. ¹  Cioaba² 

[1] Department of Mathematical Sciences, University of Delaware, 501 Ewing Hall, Newark, Delaware 19716, USA;Department of Mathematics, University of West Georgia, 1601 Maple St., Carrollton 30118, Georgia, USA

关键词: spectral graph theory;    eigenvalue;    connectivity;    toughness;    spanning $k$-tree;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity.We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.

【 授权许可】

Unknown