NORDHAUS-GADDUM-TYPE THEOREM FOR DIAMETER OF GRAPHS WHEN DECOMPOSING INTO MANY PARTS

被引：5

作者：

An, Zhihua ^{[1
]}

Wu, Baoyindureng ^{[1
]}

Li, Daobin ^{[1
]}

Wang, Yun ^{[1
]}

Su, Guifu ^{[2
]}

机构：

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

[2] Beijing Inst Technol, Dept Math, Beijing 100081, Peoples R China

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2011年 / 3卷 / 03期

关键词：

Decomposition; diameter; distance;

D O I：

10.1142/S179383091100122X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let K-n be the complete graph of order n, and k >= 2 any fixed integer. Assume (G(1), G(2),..., G(k)) is a decomposition of K-n such that Gi is connected for each i = 1, ..., k. We show that for any sufficiently large n, 2k <= Sigma(k)(i=1) diam(G(i)) = (k - 1)(n - 1) + 2, and that the bounds are best possible.

引用

页码：305 / 310

页数：6

共 15 条

[1]

Arumugam S, 1996, ARS COMBINATORIA, V43, P89

[2]

Bondy J.A., 2008, GRADUATE TEXTS MATH

[3]

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

[4] Nordhaus-Gaddum-type theorems for decompositions into many parts [J].

Füredi, Z ;

Kostochka, AV ;

Skrekovski, R ;

Stiebitz, M ;

West, DB .

JOURNAL OF GRAPH THEORY, 2005, 50 (04) :273-292

[5] SOME NORDHAUS-GADDUM-TYPE RESULTS [J].

GODDARD, W ;

HENNING, MA ;

SWART, HC .

JOURNAL OF GRAPH THEORY, 1992, 16 (03) :221-231

[6] THE DIAMETER OF A GRAPH AND ITS COMPLEMENT [J].

HARARY, F ;

ROBINSON, RW .

AMERICAN MATHEMATICAL MONTHLY, 1985, 92 (03) :211-212

[7]

Nordhaus E.A., 1956, AM MATH MONTHLY, V63, P175, DOI DOI 10.2307/2306658

[8]

Plesnik J., 1978, J GRAPH THEOR, V2, P9

[9] A map colour theorem for the union of graphs [J].

Stiebitz, M ;

Skrekovkski, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (01) :20-37

[10]

Straffin Jr P. D., 1986, AM MATH MONTHLY, V93, P76

← 1 2 →