Average distance,minimum degree,and spanning trees |
| |
Authors: | Peter Dankelmann Roger Entringer |
| |
Abstract: | 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) = ( )−1 Σ{x,y}⊂V(G) dG(x, y), where V(G) denotes the vertex set of G and dG(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 . We give improved bounds for K3‐free graphs, C4‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000 |
| |
Keywords: | graph spanning tree average distance mininum degree |
|
|