How to decrease the diameter of triangle-free graphs

被引:22
作者
Erdos, P [1 ]
Gyárfás, A [1 ]
Ruszinkó, M [1 ]
机构
[1] Hungarian Acad Sci, Comp & Automat Res Inst, H-1518 Budapest, Hungary
基金
匈牙利科学研究基金会;
关键词
AMS Subject Classification (1991) Classes:  05C12, 05C35;
D O I
10.1007/s004930050035
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Assume that G is a triangle-free graph. Let h(d)(G) be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that h(2)(G)=Theta(n log n) for connected graphs of order n and of fixed maximum degree. The proof is based on relations of h(2)(G) and the clique-cover number of edges of graphs. It is also shown that the maximum value of h(2)(G) over (triangle-free) graphs of order n is inverted right perpendicular n/2 - 1 inverted left perpendicular [n/2 - 1]. The behavior of h(3)(G) is different, its maximum value is n-1. We could not decide whether h(4)(G) less than or equal to (1- epsilon)n for connected (triangle-free) graphs of order n with a positive epsilon.
引用
收藏
页码:493 / 501
页数:9
相关论文
共 14 条
[1]   COVERING GRAPHS BY THE MINIMUM NUMBER OF EQUIVALENCE-RELATIONS [J].
ALON, N .
COMBINATORICA, 1986, 6 (03) :201-206
[2]  
ALON N, UNPUB DECREASING DIA
[3]  
DECAEN D, 1985, ANN DISCRETE MATH, V27, P257
[4]   Some old and new problems in various branches of combinatorics [J].
Erdos, P .
DISCRETE MATHEMATICS, 1997, 165 :227-231
[5]   REPRESENTATION OF A GRAPH BY SET INTERSECTIONS [J].
ERDOS, P ;
GOODMAN, AW ;
POSA, L .
CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (01) :106-&
[6]  
Erdos P., 1962, ILLINOIS J MATH, V6, P122
[7]  
FAUDREE RJ, 1990, ARS COMBINATORIA, V29B, P205
[8]   ON A CLIQUE COVERING PROBLEM OF ORLIN [J].
GREGORY, DA ;
PULLMAN, NJ .
DISCRETE MATHEMATICS, 1982, 41 (01) :97-99
[9]   ON A PROBLEM OF KATONA,G.O.H. AND TARJAN,T [J].
GYORI, E ;
KOSTOCHKA, AV .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1979, 34 (3-4) :321-327
[10]  
KEZDY AE, COMMUNICATION