Average distances in undirected graphs and the removal of vertices
type: Item
instance of: scholarly article
title: Average distances in undirected graphs and the removal of vertices
zbMATH Open document ID: 0688.05045
DOI: 10.1016/0095-8956(90)90136-N
author: Ingo Althöfer
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4127248
zbMATH Keywords: average distance
reviewed by: R. G. Stanton
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q3772252
full work available at URL: 0095-8956(90)90136-n
OpenAlex ID: W2014714030
Recommended article: Q4696891
Recommended article: Average distance in graphs with removed elements
Recommended article: Average distance in weighted graphs with removed edges
Recommended article: Average distance and vertex-connectivity
Recommended article: Q3463208
Recommended article: Average distance in graphs and eigenvalues
Recommended article: Q3090416
Recommended article: A note on the average distance of a Graph
Recommended article: The average distances in random graphs with given expected degrees
Recommended article: The Average Distance in a Random Graph with Given Expected Degrees
description: scientific article; zbMATH DE number 4127248