Minimum degree, edge-connectivity and radius

被引：7

作者：

Wu, Baoyindureng ^{[1
]}

An, Xinhui ^{[1
]}

Liu, Guojie ^{[1
]}

Yan, Guiying ^{[2
]}

Liu, Xiaoping ^{[3
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

[2] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China

[3] Xinjiang Polytech Coll, Urumqi 830000, Xinjiang, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2013年 / 26卷 / 03期

关键词：

Edge-connectivity; Radius; Minimum degree; GRAPHS; DISTANCE; DIAMETER;

D O I：

10.1007/s10878-012-9479-6

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Let G be a connected graph on na parts per thousand yen4 vertices with minimum degree delta and radius r. Then , with equality if and only if one of the following holds: (1) G is K-5, (2) G congruent to K-n \ M, where M is a perfect matching, if n is even, (3) delta = n - 3 and Delta <= n - 2, if n is odd. This solves a conjecture on the product of the edge-connectivity and radius of a graph, which was posed by Sedlar, Vukicevic, Aouchice, and Hansen.

引用

页码：585 / 591

页数：7

共 16 条

[1]

[Anonymous], 2001, Introduction to Graph Theory

[2] Using minimum degree to bound average distance [J].

Beezer, RA ;

Riegsecker, JE ;

Smith, BA .

DISCRETE MATHEMATICS, 2001, 226 (1-3) :365-371

[3] Diameter of 4-colourable graphs [J].

Czabarka, E. ;

Dankelmann, P. ;

Szekely, L. A. .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1082-1089

[4]

Dankelmann P, 2005, UTILITAS MATHEMATICA, V67, P205

[5]

Dankelmann P, 2007, UTILITAS MATHEMATICA, V73, P207

[6] Minimum size of a graph or digraph of given radius [J].

Dankelmann, Peter ;

Volkmann, Lutz .

INFORMATION PROCESSING LETTERS, 2009, 109 (16) :971-973

[7]

Dlamini G, 2003, THESIS U NATAL DURBA

[8]

ERDOS P, 1989, J COMB THEORY B, V47, P73

[9] A CHARACTERIZATION OF RADIUS-CRITICAL GRAPHS [J].

FAJTLOWICZ, S .

JOURNAL OF GRAPH THEORY, 1988, 12 (04) :529-532

[10]

He W., 1991, MATH APPL, V4, P28

← 1 2 →