Average distance, minimum degree, and spanning trees

Peter Dankelmann, Roger Entringer

Research output: Contribution to journalArticlepeer-review

66 Citations (Scopus)

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) = (n2)-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 n/δ+1 + 5. We give improved bounds for K3-free graphs, C4-free graphs, and for graphs of given girth.

Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalJournal of Graph Theory
Volume33
Issue number1
DOIs
Publication statusPublished - Jan 2000
Externally publishedYes

Keywords

  • Average distance
  • Graph
  • Mininum degree
  • Spanning tree

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Average distance, minimum degree, and spanning trees'. Together they form a unique fingerprint.

Cite this