Minimum size of a graph or digraph of given radius

被引：8

作者：

Dankelmann, Peter ^{[1
]}

Volkmann, Lutz ^{[2
]}

机构：

[1] Univ KwaZulu Natal, Sch Math Sci, ZA-4000 Durban, South Africa

[2] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52056 Aachen, Germany

来源：

INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 16期

关键词：

Interconnection networks; Graph; Digraph; Radius; Minimum degree; Size;

D O I：

10.1016/j.ipl.2009.06.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we show that a connected graph of order n, radius r and minimum degree delta has at least 1/2 (delta n + (n-1)(delta-2)/(delta-1)(r)-1) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：971 / 973

页数：3

共 15 条

[1]

Dankelmann P, 2005, UTILITAS MATHEMATICA, V67, P205

[2]

DANKELMANN P, DISTANCES K 2 UNPUB

[3]

Dankelmann P, 2007, UTILITAS MATHEMATICA, V73, P207

[4]

DANKELMANN R, NUMBER EDGES B UNPUB

[5]

Egawa Y, 1999, ARS COMBINATORIA, V51, P89

[6]

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

[7] MAXIMUM INDUCED TREES IN GRAPHS [J].

ERDOS, P ;

SAKS, M ;

SOS, VT .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :61-79

[8]

Fajtlowicz S., 1990, WRITTEN WALL CONJECT

[9]

Fajtlowicz S., 1986, Congr. Numer., V55, P51

[10]

GOLDBERG MK, 1965, USP MAT NAUK, V20, P203

← 1 2 →