论文标题
具有给定围栏或集团数字的图形的连接性和特征值
Connectivity and eigenvalues of graphs with given girth or clique number
论文作者
论文摘要
令$κ'（g）$，$κ（g）$，$μ__{n-1}（g）$和$μ_1（g）$表示边缘连接性，顶点连接性，代数连接性，laplacian Spectral Spectral Spectral Radius分别为$ G $。在本文中，我们证明，对于整数$ k \ geq 2 $和$ r \ geq 2 $，以及任何简单的图$ g $ of订单$ n $，带有最低度$δ\ geq k $，girth $ g \ geq 3 $和clique numble $ω（g）\ leq r $ \ geq \ frac {（k-1）n} {n（δ，g）（n-n（δ，g））} $或者如果$μ__{n-1}（g）\ geq \ geq \ frac {（k-1）n} n}φ（geq（k-1）N} {φ（δ（δ，r）（n-φ（n-φ（Δ，Δ）$ n（n-φ（n-;具有$δ$的简单图，带有围绕的$ g $，以及$φ（δ，r）= \ max \ {Δ+1，\ lfloor \ frac {rΔ} {r-1} {r-1} {r-1} \ rfloor \} $。涉及$μ_{n-1}（g）$和$ \ frac {μ_1（g）} {μ__{n-1}（g）} $的模拟结果，以表征具有固定Girth和Clique数字的图形的顶点连接性的表征。以前的结果[线性代数应用。 439（2013）3777--3784]，[线性代数应用。 578（2019）411--424]，[线性代数应用。 579（2019）72--88]，[应用。数学。计算。 344-345（2019）141--149]和[电子J.线性代数34（2018）428--443]得到改进或扩展。
Let $κ'(G)$, $κ(G)$, $μ_{n-1}(G)$ and $μ_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\geq 2$ and $r\geq 2$, and any simple graph $G$ of order $n$ with minimum degree $δ\geq k$, girth $g\geq 3$ and clique number $ω(G)\leq r$, the edge-connectivity $κ'(G)\geq k$ if $μ_{n-1}(G) \geq \frac{(k-1)n}{N(δ,g)(n-N(δ,g))}$ or if $μ_{n-1}(G) \geq \frac{(k-1)n}{φ(δ,r)(n-φ(δ,r))}$, where $N(δ,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $δ$-regular simple graph with girth $g$, and $φ(δ,r) = \max\{δ+1,\lfloor\frac{rδ}{r-1}\rfloor\}$. Analogue results involving $μ_{n-1}(G)$ and $\frac{μ_1(G)}{μ_{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.
