Bollobás, Béla; Chung, F. R. K. The diameter of a cycle plus a random matching. (English) Zbl 0664.05036 SIAM J. Discrete Math. 1, No. 3, 328-333 (1988). The authors’ abstract: “How small can the diameter be made by adding a matching to an n-cycle? In this paper this question is answered by showing that the graph consisting of an n-cycle and a random matching has diameter about \(\log_ 2n\), which is very close to the best possible value. It is also shown that by adding a random matching to graphs with certain expanding properties such as expanders or Ramanujan graphs, the resulting graphs have near optimum diameters.” Reviewer: R.L.Hemminger Cited in 32 Documents MSC: 05C38 Paths and cycles 05C80 Random graphs (graph-theoretic aspects) Keywords:diameter; matching; n-cycle; random matching; expanders; Ramanujan graphs PDFBibTeX XMLCite \textit{B. Bollobás} and \textit{F. R. K. Chung}, SIAM J. Discrete Math. 1, No. 3, 328--333 (1988; Zbl 0664.05036) Full Text: DOI