×

The diameter of a cycle plus a random matching. (English) Zbl 0664.05036

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

MSC:

05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI