Premium
Decreasing the diameter of cycles
Author(s) -
Grigorescu Elena
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10122
Subject(s) - mathematics , combinatorics , conjecture , graph , upper and lower bounds , discrete mathematics , mathematical analysis
Alon, Gyárfás, and Ruszinkó 1 established a bound for the minimum number of edges that have to be added to a graph of n ≥ n 0 vertices in order to obtain a graph of diameter 2. Alon et al. approximated n 0 by a polynomial function of the maximum degree of the initial graph. They conjectured that the minimum value for n 0 is 12 for the case of C n , as opposed to n 0 = 274 obtained by calculations for the general case. In this paper we prove their conjecture. For the reduction to diameter 3 of a cycle, we also improve the bounds from 1 showing that the minimum number of edges that need to be added to the cycle C n is between n − 59 and n − 8. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 299–303, 2003