图的圈边连通度和圈弧连通度

Cyclic Edge-Connectivity and Cyclic Arc-Connectivity of Graphs

令G是一个简单图.G的圈边连通度cλ(G)定义为E(G)的一个子集F的最小基数,其中G−F不连通且至少有两个分支包含圈.令D是一个有向图.D的圈弧连通度λ_(c)(D)定义为A(D)的一个子集S的最小基数,其中D−S不强连通且至少有两个强连通分支包含有向圈.在文章中,我们研究了无向二元Kautz图、无向de Bruijn图和无向二元广义de Bruijn图的圈边连通度.而且,我们获得了Kautz有向图、de Bruijn有向图和广义de Bruijn图的圈弧连通度.

Let G be a simple graph.The cyclic edge-connectivity cλ(G)is defined to be the minimum cardinality of a subset F of E(G),where G−F is disconnected and has at least two components containing cycles.Let D be a digraph.The cyclic arc-connectivityλc(D)is defined to be the minimum cardinality of a subset S of A(D),where D−S is not strongly connected and has at least two strong components containing directed cycles.In this paper,we establish the cyclic edge-connectivity of the undirected binary Kautz graphs,the undirected de Bruijn graphs and the undirected binary generalized de Bruijn graphs.Moreover,we obtain the cyclic arc-connectivity of the Kautz digraphs,the de Bruijn digraphs and the generalized de Bruijn digraphs.