The Algebraic Connectivity and the Clique Number of Graphs

Abstract

This paper investigates some relationship between the algebraic connectivity and the clique number of graphs. We characterize all extremal graphs which have the maximum and minimum the algebraic connectivity among all graphs of order $n$ with the clique number $r$, respectively. In turn, an upper and lower bounds for the clique number of a graph in terms of the algebraic connectivity are obtained. Moreover, a spectral version of the Erdős-Stone theorem in terms of the algebraic connectivity of graphs is presented.

arXiv comment18pages, 4figures

Cited by in corpus (2)

• More results on the distance (signless) Laplacian eigenvalues of graphs
• A note on algebraic connectivity of 2-connected graphs