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

朱虹州; 孟吉翔

doi:10.13568/j.cnki.651094.651316.2020.12.10.0001

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 图的圈边连通度和圈弧连通度
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 38, Issue 6, Pages: 655-664(2021)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.651316.2020.12.10.0001
  CLC： O157.5
- Published：2021
- 稿件说明：
移动端阅览
[1]朱虹州,孟吉翔.图的圈边连通度和圈弧连通度[J].新疆大学学报(自然科学版)(中英文),2021,38(06):655-664.
[1]朱虹州,孟吉翔.图的圈边连通度和圈弧连通度[J].新疆大学学报(自然科学版)(中英文),2021,38(06):655-664. DOI： 10.13568/j.cnki.651094.651316.2020.12.10.0001.

DOI：10.13568/j.cnki.651094.651316.2020.12.10.0001.

摘要

令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图的圈弧连通度.

Abstract

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.

关键词

Keywords

references

LOU D, HOLTON D. Lower bound of cyclic edge connectivity for n-extendability of regular graphs[J]. Discrete Math, 1993, 112:139-150.

ZHANG Z, ZHU Y F. Cyclic arc-connectivity in a Cartesian product digraph[J]. Applied Mathematics Letters, 2010, 23:796-800.

TAIT P. Remarks on the colouring of maps[J]. Proceedings of the Royal Society of Edinburgh, 1880, 10:501-503.

PLUMMER M. On the cyclic connectivity of planar graphs[J]. Lecture Notes in Mathematics, 1992, 303:235-242.

ZHANG C. Integer flows and cycle covers of graphs[M]. New York:Marcel Dekker Inc Publishers, 1997.

WANG B, ZHANG Z. On cyclic edge-connectivity of transitive graphs[J]. Discrete Mathematics, 2009, 309:4555-4563.

NEDELA,SKOVIERA R, MARTIN. Atoms of cyclic connectivity in cubic graphs[J]. Mathematica Slovaca, 1995, 45:481-499.

CHENG E, LIPTAK L, QIU K, et al. Cyclic vertex-connectivity of Cayley graphs generated by transposition trees[J]. Graphs and Combinatorics, 2013, 29:835-841.

QIN D J, TIAN Y Z, MENG J X. Cyclic vertex connectivity of Cartesian product cycles[J]. Journal of Xinjiang University(Natural Science Edition), 2017, 34(4):415-420.

JENSEN J, GUTIN G. Digraphs theory, algorithms and applications[M]. London:Springer Publishers, 2010.

WANG S Y, LIN S W. The maximal restricted edge connectivity of Kautz undirected graphs(extended abstract)[J]. Electron Notes in Discrete Mathematics, 2005, 22:49-53.

WANG S Y, LIN S W. The k-restricted edge connectivity of undirected Kautz graphs[J]. Discrete Mathematics, 2009, 309:4649-4652.

LYU C, ZHANG K. Super connectivity and restricted connectivity of undirected de Bruijn graphs[J]. Acta Mathematicae Applicatae Sinica, 2002, 25:29-35.

IMASE M, SONEOKA T, OKADA K. Fault-tolerant processor interconnection networks[J]. Systems and Computers in Japan,1986, 17:21-30.

OU J P, LI J Q. On m-restricted edge connectivity of undirected generalized de Bruijn graphs[J]. International Journal of Computer Mathematics, 2013, 90:2259-2264.

ZHANG J H, MENG J X. Restricted arc-connectivity of generalized de Bruijn digraphs and Kautz digraphs[J]. Journal of Xinjiang University(Natural Science Edition in Chinese and English), 2020, 37(4):415-427.

BONDY J, MURTY U. Graph theory with applications[M]. Macmillan, London:Springer Publishers, 2008.

F`ABREGA J, FIOL M. Extraconnectivity of graphs with large girth[J]. Discrete Mathematics, 1994, 127:163-170.

F`ABREGA J, FIOL M. On the extraconnectivity of graphs[J]. Discrete Mathematics, 1996, 155:49-57.

OU J P, CHENG X H, WU J C. On 3-restricted edge connectivity of undirected binary Kautz graphs[J]. Discrete Mathematics,2009, 309:629-638.

FAN Y M, XU J M. Restricted edge-connectivity of Kautz graphs[J]. Mathematicase Applicatae, 2004, 17(2):329-332.

Views

143

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

全图的圈连通度(英文)

Related Author

刘振华

黄晓晖

Related Institution

No data

⁰