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 [J].
Caporossi, G ;
Hansen, P .
DISCRETE MATHEMATICS, 2004, 276 (1-3) :81-94
[8]   Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system [J].
Caporossi, G ;
Hansen, P .
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
123