论文标题
极端循环边缘连接性的光谱阈值
Spectral Threshold for Extremal Cyclic Edge-Connectivity
论文作者
论文摘要
图$ g $的循环边缘连接性是最少$ k $的，因此存在一组$ k $的边缘，其删除将$ g $断开到每个组件包含一个周期的组件中。我们表明，对于至少3和围栏$ g $的最低图表至少4个，环状边缘连接性在上面的$（δ-2）g $中，其中$δ$是最高度。然后，我们证明，如果$ d $的邻接矩阵的第二个特征值的周长$ g \ geq4 $足够小，则循环边缘连接性为$（d-2）g $，当这种环状边缘连接性上的上限时，它提供了光谱条件。
The cyclic edge-connectivity of a graph $G$ is the least $k$ such that there exists a set of $k$ edges whose removal disconnects $G$ into components where every component contains a cycle. We show that for graphs of minimum degree at least 3 and girth $g$ at least 4, the cyclic edge-connectivity is bounded above by $(Δ-2)g$ where $Δ$ is the maximum degree. We then prove that if the second eigenvalue of the adjacency matrix of a $d$-regular graph of girth $g\geq4$ is sufficiently small, then the cyclic edge-connectivity is $(d-2)g$, providing a spectral condition for when this upper bound on cyclic edge-connectivity is tight.
