THE MAXIMUM NUMBER OF EDGES IN A MINIMAL GRAPH OF DIAMETER-2

被引：35
作者：
FUREDI, Z
机构：
[1] HUNGARIAN ACAD SCI,INST MATH,H-1364 BUDAPEST,HUNGARY
[2] UNIV MINNESOTA,INST MATH & APPLICAT,MINNEAPOLIS,MN 55455
来源：
JOURNAL OF GRAPH THEORY | 1992年 / 16卷 / 01期
关键词：
D O I：
10.1002/jgt.3190160110
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph G of diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved for n > n0. If G has n vertices then it has at most [n2/4] edges. The only extremum is the complete bipartite graph.
引用
收藏
页码：81 / 98
页数：18
相关论文
共 11 条
[1]  
Bollobas B., 1978, LONDON MATH SOC MONO
[2]   DIAMETER CRITICAL GRAPHS [J].
CACCETTA, L ;
HAGGKVIST, R .
DISCRETE MATHEMATICS, 1979, 28 (03) :223-229
[3]  
Chung Fan, 1986, P S APPL MATH, V34, P1
[4]  
DUKE R, IN PRESS J COMBINA A
[5]  
Erds P, 1968, J COMB THEORY, V5, P164, DOI [10.1016/S0021-9800(68)80051-1, DOI 10.1016/S0021-9800(68)80051-1.]
[6]   ON DIAMETER 2-CRITICAL GRAPHS [J].
FAN, G .
DISCRETE MATHEMATICS, 1987, 67 (03) :235-240
[7]  
Plesnik J., 1975, ACTA FAC RERUM NAT U, V30, P71
[8]  
RUZSA IZ, 1978, COMBINATORICA, P939
[9]  
Szemeredi E., 1976, C INT CNRS, V260, P399
[10]  
XU J, 1984, J MATH RES EXPOSITIO, V4, P85
12