The cubic graphs with finite cyclic vertex connectivity larger than girth
The cubic graphs with finite cyclic vertex connectivity larger than girth
复制标题
DOI：
10.1016/j.disc.2020.112197
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Jun Liang;Dingjun Lou;Zan-Bo Zhang
中科院分区：
文献类型：
--
作者：
Jun Liang;Dingjun Lou;Zan-Bo Zhang
循环（顶点和边）连通性是图中的一个重要概念。虽然循环边连通性（c λ）已经研究了很多年，但循环顶点连通性（c κ）的研究仍处于起步阶段。而且c κ 似乎比c λ 更复杂。我们得到了一个充分条件：对于 c κ≠∞，ν (G)≥ 2 g (k− 1)。另一方面，如果 ν (G)< 2 g (k− 1)，则有 c κ=∞，或 c κ≤(k− 2) g，或 (k− 2) g< c κ < Infini。因此，用 (k− 2) g< c κ < ∞ 来表征所有 k-正则图有助于设计 c κ 的有效算法。因此，我们用 g< c κ < Infini 来表征所有 38 个三次图，并证明 c κ= g+ 1。
Cyclic (vertex and edge) connectivity is an important concept in graphs. While cyclic edge connectivity (c λ) has been studied for many years, the study at cyclic vertex connectivity (c κ) is still at the initial stage. And c κ seems to be more complicated than c λ. We have got a sufficient condition that ν (G)≥ 2 g (k− 1) for c κ≠∞. On the other hand, if ν (G)< 2 g (k− 1), then we have c κ=∞, or c κ≤(k− 2) g, or (k− 2) g< c κ<∞. So characterizing all the k-regular graphs with (k− 2) g< c κ<∞ is helpful to design an efficient algorithm for c κ. Hence, we characterize all 38 cubic graphs with g< c κ<∞ and prove that c κ= g+ 1.