李積慶，歐見(jiàn)平

?

無(wú)向廣義De Bruijn圖的-限制邊連通性

李積慶，歐見(jiàn)平

（五邑大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣東 江門(mén) 529020）

廣義De Bruijn圖；邊割；限制邊連通度

1 結(jié)構(gòu)刻畫(huà)及預(yù)備引理

圖1 無(wú)向廣義De Bruijn圖

首先考慮情況1）：

同理，可以證明情況2）和3）的假設(shè)也是不成立的，引理得證.

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

國(guó)家自然科學(xué)基金資助項(xiàng)目（10801091；11126326）

李積慶（1985—），男，山西大同人，在讀碩士生，研究方向?yàn)閳D論及其應(yīng)用；歐見(jiàn)平，教授，博士，碩士生導(dǎo)師，通信作者，研究方向?yàn)榻M合圖論.