Premium
Average distance, minimum degree, and spanning trees
Author(s) -
Dankelmann Peter,
Entringer Roger
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200001)33:1<1::aid-jgt1>3.0.co;2-l
Subject(s) - combinatorics , mathematics , spanning tree , vertex (graph theory) , degree (music) , graph , connectivity , discrete mathematics , physics , acoustics
The average distance μ( G ) of a connected graph G of order n is the average of the distances between all pairs of vertices of G , i.e., μ( G ) = ( n 2 ) −1 Σ { x,y }⊂ V ( G ) d G ( x, y ), where V ( G ) denotes the vertex set of G and d G ( x, y ) is the distance between x and y . We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most $${n\over \delta + 1} + 5$$ . We give improved bounds for K 3 ‐free graphs, C 4 ‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000