无向广义De Bruijn图的m-限制边连通性

李积庆，欧见平



无向广义De Bruijn图的-限制边连通性

李积庆，欧见平

（五邑大学 数学与计算科学学院，广东 江门 529020）

广义De Bruijn图；边割；限制边连通度

1 结构刻画及预备引理

图1 无向广义De Bruijn图

首先考虑情况1）：

同理，可以证明情况2）和3）的假设也是不成立的，引理得证.

2 极大m-限制边连通性

[1] MOORE E F, SHANNON C. Reliable circuits using less reliable relays[J]. J Franklin Inst, 1956, 262: 191-208.

[2] PROVAN J S, BALL M O. The complexity of counting cuts and of computing the probability that a graph is connected[J]. SIAM J Comput, 1983, 12: 777-788.

[3] BAUER D, BOESCH F, SUFFEL C. Combinatorial optimization problems in analysis and design of probabilistic network[J]. Networks, 1985, 15: 257-271.

[4] ESFAHANIAN A H, HAKIMI S L. On computing a conditional edge connectivity of a graph[J]. Inform Process Lett, 1988, 27: 195-199.

[5] BONSMA P, UEFFING N, BOLKMNN L. Edge-cuts leaving components of order at least three[J]. Discrete Math, 2002, 256: 431-439.

[7] LI Liangqiao, LI Qiao. Reliability analysis of circulant graphs[J]. Networks, 1988, 28: 61-65.

[8] WANG Ming, LI Qiao. Conditional edge connectivity properties, reliability comparison and transitivity of graphs[J]. Discrete Math, 2002, 258: 205-214.

[10] MENG Jixiang, JI Youhu. On a kind of restricted edge connectivity of graphs[J]. Discrete Appl Math, 2002, 117: 183-193.

[11] OU Jianping, ZHANG Fuji. 3-restricted edge connectivity of vertex transitive graphs[J]. Ars Combin, 2005, 74: 291-302.

[12] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: Elserier, 1976.

[13] OU Jianping. On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks[J]. Appl Math Comput, 2010, 217: 2602-2607.

[14] HOMOBONO N. Connectivity of generalized de Bruijn graphs[J]. Ars Combin, 1988, 25: 179-194.

[15] HELLWIG A, BOLKMANN L. Maximally edge-connected and vertex-connected graphs and digraphs[J]. Discrete Math, 2008, 308: 3265-3296.

[16] DU D Z, HSU D F, HWANG F K, et al. The hamiltonian property of generalized De Bruijn digraphs[J]. J Combin Ser(B), 1991, 52: 1-8.

[18] OU Jianping, ZHANG Fuji. Reliability of undirected De Bruijn networks[J]. Chinese Journal of Engineering Mathematics, 2004, 21: 945-952.

The-restricted Edge Connectivity of Undirected Generalized De Bruijn Graphs

LIJi-qing, OUJian-ping

(School of Mathematics and Computation Science, Wuyi University, Jiangmen 529020, China)

generalized De Bruijn graphs; edge cut; restricted edge connectivity

1006-7302（2012）03-0006-06

O157.5

A

2012-03-02

国家自然科学基金资助项目（10801091；11126326）

李积庆（1985—），男，山西大同人，在读硕士生，研究方向为图论及其应用；欧见平，教授，博士，硕士生导师，通信作者，研究方向为组合图论.