Diameter and inverse degree

Peter Dankelmann; Henda C. Swart; Paul van den Berg

doi:10.1016/j.disc.2007.07.053

Diameter and inverse degree

Peter Dankelmann
, Henda C. Swart
, Paul van den Berg

University of KwaZulu-Natal

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

30 Citations (Scopus)

Abstract

The inverse degree r (G) of a finite graph G = (V, E) is defined as r (G) = ∑_{v ∈ V} frac(1, deg v). We prove that, if G is connected and of order n, then the diameter of G is less than (3 r (G) + 2 + o (1)) frac(log n, log log n). This improves a bound given by Erdös et al. by a factor of approximately 2.

Original language	English
Pages (from-to)	670-673
Number of pages	4
Journal	Discrete Mathematics
Volume	308
Issue number	5-6
DOIs	https://doi.org/10.1016/j.disc.2007.07.053
Publication status	Published - 28 Mar 2008
Externally published	Yes

Keywords

Diameter
Distance
Inverse degree

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.07.053

Cite this

@article{6bed6a922b1f46168279c74e5d733d9a,

title = "Diameter and inverse degree",

abstract = "The inverse degree r (G) of a finite graph G = (V, E) is defined as r (G) = ∑v ∈ V frac(1, deg v). We prove that, if G is connected and of order n, then the diameter of G is less than (3 r (G) + 2 + o (1)) frac(log n, log log n). This improves a bound given by Erd{\"o}s et al. by a factor of approximately 2.",

keywords = "Diameter, Distance, Inverse degree",

author = "Peter Dankelmann and Swart, \{Henda C.\} and \{van den Berg\}, Paul",

year = "2008",

month = mar,

day = "28",

doi = "10.1016/j.disc.2007.07.053",

language = "English",

volume = "308",

pages = "670--673",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5-6",

}

TY - JOUR

T1 - Diameter and inverse degree

AU - Dankelmann, Peter

AU - Swart, Henda C.

AU - van den Berg, Paul

PY - 2008/3/28

Y1 - 2008/3/28

N2 - The inverse degree r (G) of a finite graph G = (V, E) is defined as r (G) = ∑v ∈ V frac(1, deg v). We prove that, if G is connected and of order n, then the diameter of G is less than (3 r (G) + 2 + o (1)) frac(log n, log log n). This improves a bound given by Erdös et al. by a factor of approximately 2.

AB - The inverse degree r (G) of a finite graph G = (V, E) is defined as r (G) = ∑v ∈ V frac(1, deg v). We prove that, if G is connected and of order n, then the diameter of G is less than (3 r (G) + 2 + o (1)) frac(log n, log log n). This improves a bound given by Erdös et al. by a factor of approximately 2.

KW - Diameter

KW - Distance

KW - Inverse degree

UR - https://www.scopus.com/pages/publications/38049129624

U2 - 10.1016/j.disc.2007.07.053

DO - 10.1016/j.disc.2007.07.053

M3 - Article

AN - SCOPUS:38049129624

SN - 0012-365X

VL - 308

SP - 670

EP - 673

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5-6

ER -

Diameter and inverse degree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this