Average distance, minimum degree, and spanning trees

Peter Dankelmann; Roger Entringer

doi:10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L

Average distance, minimum degree, and spanning trees

Peter Dankelmann, Roger Entringer

Research output: Contribution to journal › Article › peer-review

67 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) = (ⁿ₂)^-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/δ+1 + 5. We give improved bounds for K₃-free graphs, C₄-free graphs, and for graphs of given girth.

Original language	English
Pages (from-to)	1-13
Number of pages	13
Journal	Journal of Graph Theory
Volume	33
Issue number	1
DOIs	https://doi.org/10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L
Publication status	Published - Jan 2000
Externally published	Yes

Keywords

Average distance
Graph
Mininum degree
Spanning tree

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L

Cite this

@article{cd858d8eaf1f4416b0df2f5ee01e4331,

title = "Average distance, minimum degree, and spanning trees",

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.",

keywords = "Average distance, Graph, Mininum degree, Spanning tree",

author = "Peter Dankelmann and Roger Entringer",

year = "2000",

month = jan,

doi = "10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L",

language = "English",

volume = "33",

pages = "1--13",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Average distance, minimum degree, and spanning trees

AU - Dankelmann, Peter

AU - Entringer, Roger

PY - 2000/1

Y1 - 2000/1

N2 - 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.

AB - 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.

KW - Average distance

KW - Graph

KW - Mininum degree

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=0034409871&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L

DO - 10.1002/(SICI)1097-0118(200001)33:1<1::AID-JGT1>3.0.CO;2-L

M3 - Article

AN - SCOPUS:0034409871

SN - 0364-9024

VL - 33

SP - 1

EP - 13

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Average distance, minimum degree, and spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this