Sufficient conditions for maximally restricted edge connected graphs

被引：1

作者：

Qin, Yingying ^{[1
]}

Ou, Jianping ^{[1
]}

机构：

[1] Wuyi Univ, Dept Math, Jiangmen 529020, Peoples R China

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 19期

基金：

中国国家自然科学基金;

关键词：

Restricted edge connectivity; Degree sequence;

D O I：

10.1016/j.disc.2012.05.008

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown in this work that if graph G has degree sequence d(1) >= d(2) >= ... >= d(n) >= 2 with Sigma(l)(i=1)(d(i) + d(n-i-1)) > l(n + 2) holding for every 1 <= l <= n/2 - 2, then it is lambda'-optimal. The lower bound on the degree-summation is exemplified sharp. This observation generalizes the corresponding results of Bollobas on maximal edge connectivity of graphs. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：2969 / 2972

页数：4

共 16 条

[1] Sufficient conditions for λ′-optirnality in graphs with girth g
Balbuena, C
García-Vázquez, P
Marcote, X
[J]. JOURNAL OF GRAPH THEORY, 2006, 52 (01) : 73 - 86
[2] COMBINATORIAL OPTIMIZATION PROBLEMS IN THE ANALYSIS AND DESIGN OF PROBABILISTIC NETWORKS
BAUER, D
BOESCH, F
SUFFEL, C
TINDELL, R
[J]. NETWORKS, 1985, 15 (02) : 257 - 271
[3] GRAPHS WITH EQUAL EDGE CONNECTIVITY AND MINIMUM DEGREE
BOLLOBAS, B
[J]. DISCRETE MATHEMATICS, 1979, 28 (03) : 321 - 323
[4] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[5] ON COMPUTING A CONDITIONAL EDGE-CONNECTIVITY OF A GRAPH
ESFAHANIAN, AH
HAKIMI, SL
[J]. INFORMATION PROCESSING LETTERS, 1988, 27 (04) : 195 - 199
[6] EXTRACONNECTIVITY OF GRAPHS WITH LARGE GIRTH
FABREGA, J
FIOL, MA
[J]. DISCRETE MATHEMATICS, 1994, 127 (1-3) : 163 - 170
[7] Sufficient conditions for graphs to be λ′-optimal super-edge-connected and maximally edge-connected
Hellwig, A
Volkmann, L
[J]. JOURNAL OF GRAPH THEORY, 2005, 48 (03) : 228 - 246
[8] Maximally edge-connected and vertex-connected graphs and digraphs: A survey
Hellwig, Angelika
Volkmann, Lutz
[J]. DISCRETE MATHEMATICS, 2008, 308 (15) : 3265 - 3296
[9] Li QL, 1998, NETWORKS, V31, P61, DOI 10.1002/(SICI)1097-0037(199803)31:2<61::AID-NET1>3.0.CO
[10] 2-H

← 1 2 →