A survey of Nordhaus-Gaddum type relations

被引：128
作者：
Aouchiche, Mustapha [1 ]
Hansen, Pierre
机构：
[1] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada
来源：
DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 4-5期
关键词：
Nordhaus-Gaddum; Graph; Complement; Inequalities; Invariants; VARIABLE NEIGHBORHOOD SEARCH; ATOM-BOND CONNECTIVITY; GEOMETRIC. ARITHMETIC INDEX; TOTAL RESTRAINED DOMINATION; RECIPROCAL DISTANCE MATRIX; LINEAR VERTEX-ARBORICITY; INDUCED PATH NUMBER; UPPER-BOUNDS; EXTREMAL GRAPHS; COMPLEMENTARY GRAPHS;
D O I：
10.1016/j.dam.2011.12.018
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the order of the graph. Since then, relations of a similar type have been proposed for many other graph invariants, in several hundred papers. We present a survey on this research endeavor. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：466 / 546
页数：81
相关论文
共 359 条
[1]  
Achuthan N., 1990, AUSTRALAS J COMBIN, V2, P5
[2]  
Achuthan N., 1998, J COMBIN MATH COMBIN, V27, P107
[3]  
Achuthan N., 1996, AUSTRALAS J COMBIN, V13, P175
[4]  
Achuthan N., 2003, ELECT NOTES DISCRETE, V15, P12
[5]  
Achuthan N., 1980, ANN DISCRETE MATH, V9, P285
[6]  
Achuthan N, 2011, AUSTRALAS J COMB, V49, P3
[7]   Inequalities of Nordhaus-Gaddum type for doubly connected domination number [J].
Akhbari, M. H. ;
Hasni, R. ;
Favaron, O. ;
Karami, H. ;
Sheikholeslami, S. M. .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (14) :1465-1470
[8]   ON LINEAR VERTEX-ARBORICITY OF COMPLEMENTARY GRAPHS [J].
ALAVI, Y ;
LIU, JQ ;
WANG, JF .
JOURNAL OF GRAPH THEORY, 1994, 18 (03) :315-322
[9]  
Alavi Y, 1997, UTILITAS MATHEMATICA, V52, P43
[10]   COMPLEMENTARY GRAPHS AND EDGE CHROMATIC NUMBERS [J].
ALAVI, Y ;
BEHZAD, M .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1971, 20 (02) :161-&
12345678910