Using minimum degree to bound average distance

被引：31

作者：

Beezer, RA ^{[1
]}

Riegsecker, JE ^{[1
]}

Smith, BA ^{[1
]}

机构：

[1] Univ Puget Sound, Dept Math & Comp Sci, Tacoma, WA 98416 USA

来源：

DISCRETE MATHEMATICS | 2001年 / 226卷 / 1-3期

关键词：

graph; regular graph; average distance; minimum degree; Graffiti;

D O I：

10.1016/S0012-365X(00)00156-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show the average distance mu of a connected graph with n vertices, e edges and minimum degree d satisfies [(n+1)n(n-1)-2e/d+1]/n(n-1) This improves conjectures of the computer program Graffti (Fajtlowicz, Written on the wall, Conjectures made by program Graffiti, University of Houston, 1990), and He and Li (Math. Appl. 4 (1991) 28-34) and the results of Kouider and Winkler (J. Graph Theory 25 (1997) 95 -99). The bound is sharp since complete graphs yield equality. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：365 / 371

页数：7

共 20 条

[1] GRAPH INVARIANTS FOR FULLERENES [J].

BALABAN, AT ;

LIU, X ;

KLEIN, DJ ;

BABIC, D ;

SCHMALZ, TG ;

SEITZ, WA ;

RANDIC, M .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1995, 35 (03) :396-404

[2]

BEEZER RA, 1989, 891 U PUG DEP MATH C

[3]

Bermond JC, 1997, NETWORKS, V30, P187, DOI 10.1002/(SICI)1097-0037(199710)30:3<187::AID-NET4>3.0.CO

[4]

2-H

[5] AVERAGE DISTANCE IN GRAPHS WITH REMOVED ELEMENTS [J].

BIENSTOCK, D ;

GYORI, E .

JOURNAL OF GRAPH THEORY, 1988, 12 (03) :375-390

[6]

Buckley F., 1981, Congr. Numer., V32, P153

[7]

Buckley F., 1981, P 3 CARIBBEAN C COMB, P67

[8] THE AVERAGE DISTANCE AND THE INDEPENDENCE NUMBER [J].

CHUNG, FRK .

JOURNAL OF GRAPH THEORY, 1988, 12 (02) :229-235

[9]

Fajtlowicz S., 1990, WRITTEN WALL CONJECT

[10]

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

← 1 2 →