Average distance, minimum degree, and size

Peter Dankelmann

Average distance, minimum degree, and size

Peter Dankelmann

University of KwaZulu-Natal

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

4 Citations (Scopus)

Abstract

We give an upper bound on the average distance of a. connected graph of given order, size, diameter, and minimum degree. As a corollary we show that the average distance of a connected graph of order n, size q and minimum degree δ ≥ 2 is at most ((n - √2q - ≥n)²(n + 2√2q - δn)) / ((δ + 1)n²)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.

Original language	English
Pages (from-to)	233-243
Number of pages	11
Journal	Utilitas Mathematica
Volume	69
Publication status	Published - Mar 2006
Externally published	Yes

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty
Applied Mathematics

Cite this

@article{3afd0fd90e844ea9b06f2d65548c468b,

title = "Average distance, minimum degree, and size",

abstract = "We give an upper bound on the average distance of a. connected graph of given order, size, diameter, and minimum degree. As a corollary we show that the average distance of a connected graph of order n, size q and minimum degree δ ≥ 2 is at most ((n - √2q - ≥n)2(n + 2√2q - δn)) / ((δ + 1)n2)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.",

author = "Peter Dankelmann",

year = "2006",

month = mar,

language = "English",

volume = "69",

pages = "233--243",

journal = "Utilitas Mathematica",

issn = "0315-3681",

publisher = "Utilitas Mathematica Publishing Inc.",

}

TY - JOUR

T1 - Average distance, minimum degree, and size

AU - Dankelmann, Peter

PY - 2006/3

Y1 - 2006/3

N2 - We give an upper bound on the average distance of a. connected graph of given order, size, diameter, and minimum degree. As a corollary we show that the average distance of a connected graph of order n, size q and minimum degree δ ≥ 2 is at most ((n - √2q - ≥n)2(n + 2√2q - δn)) / ((δ + 1)n2)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.

AB - We give an upper bound on the average distance of a. connected graph of given order, size, diameter, and minimum degree. As a corollary we show that the average distance of a connected graph of order n, size q and minimum degree δ ≥ 2 is at most ((n - √2q - ≥n)2(n + 2√2q - δn)) / ((δ + 1)n2)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.

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

M3 - Article

AN - SCOPUS:33646532451

SN - 0315-3681

VL - 69

SP - 233

EP - 243

JO - Utilitas Mathematica

JF - Utilitas Mathematica

ER -

Average distance, minimum degree, and size

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this