Connectivity and eigenvalues of graphs with given girth or clique number

Abstract

Let ${\kappa }^{\prime }(G)$, $\kappa (G)$, ${\mu }_{n-1}(G)$ and ${\mu }_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $k\ge 2$ and $r\ge 2$, and any simple graph $G$ of order $n$ with minimum degree $\delta \ge k$, girth $g\ge 3$ and clique number $\omega (G)\le r$, the edge-connectivity ${\kappa }^{\prime }(G)\ge k$ if ${\mu }_{n-1}(G)\ge \frac{(k-1)n}{N(\delta ,g)(n-N(\delta ,g))}$ or if ${\mu }_{n-1}(G)\ge \frac{(k-1)n}{\phi (\delta ,r)(n-\phi (\delta ,r))}$, where $N(\delta ,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $\delta$-regular simple graph with girth $g$, and $\phi (\delta ,r)=\max \{\delta +1,\lfloor \frac{r\delta }{r-1}\rfloor \}$. Analogue results involving ${\mu }_{n-1}(G)$ and $\frac{{\mu }_1(G)}{{\mu }_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended.

14 pages

References in corpus (1)

• Edge-connectivity in regular multigraphs from eigenvalues