Average distances in undirected graphs and the removal of vertices (Q1263601): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q587392
Set OpenAlex properties.
 
(3 intermediate revisions by 3 users not shown)
Property / reviewed by
 
Property / reviewed by: Ralph G.Stanton / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3941433 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3772252 / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0095-8956(90)90136-n / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2014714030 / rank
 
Normal rank

Latest revision as of 10:53, 30 July 2024

scientific article
Language Label Description Also known as
English
Average distances in undirected graphs and the removal of vertices
scientific article

    Statements

    Average distances in undirected graphs and the removal of vertices (English)
    0 references
    0 references
    1990
    0 references
    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.
    0 references
    average distance
    0 references
    0 references
    0 references

    Identifiers