On the connectivity and superconnected graphs with small diameter

被引：5

作者：

Balbuena, C. ^{[1
]}

Marshall, K. ^{[2
]}

Montejano, L. P. ^{[1
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 3, E-08034 Barcelona, Spain

[2] Univ Newcastle, Sch Elect Engn & Comp Sci, Callaghan, NSW 2308, Australia

来源：

DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 05期

关键词：

Connectivity; Superconnected; Diameter; Girth; DIGRAPHS;

D O I：

10.1016/j.dam.2009.10.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, first we prove that any graph G is 2-connected if diam(G) <= g - 1 for even girth g, and for odd girth g and maximum degree Delta <= 2 delta - 1 where delta is the minimum degree. Moreover, we prove that any graph G of diameter diam(G) <= g - 2 satisfies that (i) G is 5-connected for even girth g and Delta <= 2 delta - 5, and (ii) G is super-kappa for odd girth g and Delta <= 3 delta/2 - 1. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：397 / 403

页数：7

共 15 条

[1] Lower connectivities of regular graphs with small diameter [J].

Balbuena, C. ;

Marcote, X. .

DISCRETE MATHEMATICS, 2007, 307 (11-12) :1255-1265

[2] On the restricted connectivity and superconnectivity in graphs with given girth [J].

Balbuena, C. ;

Cera, M. ;

Dianez, A. ;

Garcia-Vazquez, P. ;

Marcote, X. .

DISCRETE MATHEMATICS, 2007, 307 (06) :659-667

[3]

Balbuena C, 1996, NETWORKS, V28, P97, DOI 10.1002/(SICI)1097-0037(199609)28:2<97::AID-NET3>3.0.CO

[4]

2-7

[5] Superconnectivity of regular graphs with small diameter [J].

Balbuena, Camino ;

Tang, Jianmin ;

Marshall, Kim ;

Lin, Yuqing .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) :1349-1353

[6]

Bauer D., 1981, The Theory and Application of Graphs, P89

[7] CIRCULANTS AND THEIR CONNECTIVITIES [J].

BOESCH, F ;

TINDELL, R .

JOURNAL OF GRAPH THEORY, 1984, 8 (04) :487-499

[8] SYNTHESIS OF RELIABLE NETWORKS - A SURVEY [J].

BOESCH, FT .

IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) :240-246

[9]

Chartrand G., 1996, Graphs & Digraphs, V3rd

[10] MAXIMALLY CONNECTED DIGRAPHS [J].

FABREGA, J ;

FIOL, MA .

JOURNAL OF GRAPH THEORY, 1989, 13 (06) :657-668

← 1 2 →