×

Average distances in undirected graphs and the removal of vertices. (English) Zbl 0688.05045

P. M. Winkler conjectured that every connected graph G contains a vertex k such that the removal of k and all incident edges enlarges the average distance between vertices of G by at most the factor 4/3. The authors prove that every m-connected graph was a vertex whose removal increases the average distance in the graph by no more than a factor of \(m/(m-1).\) This proves Winkler’s conjecture for 4-connected graphs.
Reviewer: R.G.Stanton

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., (Graphs and Hypergraphs (1976), North-Holland: North-Holland Amsterdam) · Zbl 0483.05029
[2] Winkler, P. M., Mean distance and the “Four-thirds Conjecture,”, (Congr. Numer., 54 (1986)), 63-72
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.