Assume that G is a triangle-free graph. Let 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 for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: October 12, 1997
Rights and permissions
About this article
Cite this article
Erdős, P., Gyárfás, A. & Ruszinkó, M. How to decrease the diameter of triangle-free graphs. Combinatorica 18, 493–501 (1998). https://doi.org/10.1007/s004930050035
Issue Date:
DOI: https://doi.org/10.1007/s004930050035