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

Cyclic Edge-Connectivity and Cyclic Arc-Connectivity of Graphs

作　　者：朱虹州 孟吉翔[1] ZHU Hongzhou;MENG Jixiang(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）（中英文）》2021年第6期655-664,共10页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：新疆维吾尔自治区应用数学重点实验室开放课题(2020D04046).

摘　　要：令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.

关 键 词：圈边连通度 圈弧连通度 deBruijn图 Kautz图 广义de Bruijn图 

分 类 号：O157.5[理学—数学]