Nordhaus-Gaddum relations for proximity and remoteness in graphs

被引：27

作者：

Aouchiche, M. ^{[1
]}

Hansen, P.

机构：

[1] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2010年 / 59卷 / 08期

关键词：

Nordhaus-Gaddum; Proximity; Remoteness; Extremal graph; VARIABLE NEIGHBORHOOD SEARCH; EXTREMAL GRAPHS; RADIUS;

D O I：

10.1016/j.camwa.2010.02.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：2827 / 2835

页数：9

共 23 条

[1] AOUCHICHE M, 2007, TRENDS MATH, V6, P21
[2] AOUCHICHE M, 2005, ELECT NOTES DISCRETE, V22, P515, DOI DOI 10.1016/J.ENDM.2005.06.090
[3] AOUCHICHE M, NETWORKS IN PRESS
[4] Aouchiche M, 2006, VARIABLE NEIGHBORHOO, P281
[5] Aouchiche M., 2006, Ph.D. thesis
[6] Aouchiche M, 2007, MATCH-COMMUN MATH CO, V58, P365
[7] Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures
Caporossi, G
Hansen, P
[J]. DISCRETE MATHEMATICS, 2004, 276 (1-3) : 81 - 94
[8] Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system
Caporossi, G
Hansen, P
[J]. DISCRETE MATHEMATICS, 2000, 212 (1-2) : 29 - 44
[9] Cockayne E. J., 2003, Journal of Combinatorial Mathematics and Combinatorial Computing, V47, P213
[10] Dankelmann P, 2004, UTILITAS MATHEMATICA, V65, P41

← 1 2 3 →