The average connectivity of a graph

被引：89

作者：

Beineke, LW ^{[1
]}

Oellermann, OR

Pippert, RE

机构：

[1] Indiana Univ Purdue Univ, Dept Math, Ft Wayne, IN 46805 USA

[2] Univ Winnipeg, Winnipeg, MB R3B 2E9, Canada

来源：

DISCRETE MATHEMATICS | 2002年 / 252卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

connectivity; average;

D O I：

10.1016/S0012-365X(01)00180-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we consider the concept of the average connectivity of a graph, defining it to be the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. Our main results are sharp bounds on the value of this parameter, and a construction of graphs whose average connectivity is the same as the connectivity. Along the way, we establish some new results on connectivity. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：31 / 45

页数：15

共 8 条

[1] A CLASSIFICATION SCHEME FOR VULNERABILITY AND RELIABILITY PARAMETERS OF GRAPHS [J].

BAGGA, KS ;

BEINEKE, LW ;

PIPPERT, RE ;

LIPMAN, MJ .

MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (11) :13-16

[2]

Chartrand G, 1992, APPL ALGORITHMIC GRA

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

CHUNG, FRK .

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

[4] MAXIMUM CONNECTIVITY OF A GRAPH [J].

HARARY, F .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1962, 48 (07) :1142-&

[5] CORNERS OF NTH DEGREE IN MINIMAL N-CONNECTED GRAPHS [J].

MADER, W .

ARCHIV DER MATHEMATIK, 1972, 23 (02) :219-&

[6]

Mader W., 1979, LONDON MATH SOC LECT, V38, P66, DOI [10.1017/cbo9780511662133.005, DOI 10.1017/CBO9780511662133.005]

[7]

Oellermann O. R., 1996, C NUMER, V116, P231

[8] ON THE SUM OF ALL DISTANCES IN A GRAPH OR DIGRAPH [J].

PLESNIK, J .

JOURNAL OF GRAPH THEORY, 1984, 8 (01) :1-21

← 1 →