Upper bounds on distance measures in K3,3-free graphs

Peter Dankelmann; Gcina Dlamini; Henda C. Swart

Upper bounds on distance measures in K_3,3-free graphs

Peter Dankelmann, Gcina Dlamini, Henda C. Swart

University of KwaZulu-Natal

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

15 Citations (Scopus)

Abstract

Let G be a connected graph of order n and minimum degree S. Erdös, Fach, Pollack and Tuza showed that the well known upper bounds [3n/δ+1] - 1 and 2/3 n-3/δ+1 + 5 on the diameter and radius, respectively, can be improved to bounds of the order of magnitude O(n/δ2) for C ₄-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C₄-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K_3,3-free graphs. The bounds are of the order of magnitude O(n/δ3/2) We construct graphs that show that the order of magnitude is best possible.

Original language	English
Pages (from-to)	205-221
Number of pages	17
Journal	Utilitas Mathematica
Volume	67
Publication status	Published - May 2005
Externally published	Yes

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty
Applied Mathematics

Cite this

@article{3950bb15144744f5aeaf8c1f3084cccb,

title = "Upper bounds on distance measures in K3,3-free graphs",

abstract = "Let G be a connected graph of order n and minimum degree S. Erd{\"o}s, Fach, Pollack and Tuza showed that the well known upper bounds [3n/δ+1] - 1 and 2/3 n-3/δ+1 + 5 on the diameter and radius, respectively, can be improved to bounds of the order of magnitude O(n/δ2) for C 4-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C4-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K3,3-free graphs. The bounds are of the order of magnitude O(n/δ3/2) We construct graphs that show that the order of magnitude is best possible.",

author = "Peter Dankelmann and Gcina Dlamini and Swart, {Henda C.}",

year = "2005",

month = may,

language = "English",

volume = "67",

pages = "205--221",

journal = "Utilitas Mathematica",

issn = "0315-3681",

publisher = "Utilitas Mathematica Publishing Inc.",

}

TY - JOUR

T1 - Upper bounds on distance measures in K3,3-free graphs

AU - Dankelmann, Peter

AU - Dlamini, Gcina

AU - Swart, Henda C.

PY - 2005/5

Y1 - 2005/5

N2 - Let G be a connected graph of order n and minimum degree S. Erdös, Fach, Pollack and Tuza showed that the well known upper bounds [3n/δ+1] - 1 and 2/3 n-3/δ+1 + 5 on the diameter and radius, respectively, can be improved to bounds of the order of magnitude O(n/δ2) for C 4-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C4-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K3,3-free graphs. The bounds are of the order of magnitude O(n/δ3/2) We construct graphs that show that the order of magnitude is best possible.

AB - Let G be a connected graph of order n and minimum degree S. Erdös, Fach, Pollack and Tuza showed that the well known upper bounds [3n/δ+1] - 1 and 2/3 n-3/δ+1 + 5 on the diameter and radius, respectively, can be improved to bounds of the order of magnitude O(n/δ2) for C 4-free graphs. Dankelmann and Entringer gave an analogous bound for the average distance in C4-free graphs. In this paper, we give upper bounds on the diameter, radius and average distance of K3,3-free graphs. The bounds are of the order of magnitude O(n/δ3/2) We construct graphs that show that the order of magnitude is best possible.

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

M3 - Article

AN - SCOPUS:19744370207

SN - 0315-3681

VL - 67

SP - 205

EP - 221

JO - Utilitas Mathematica

JF - Utilitas Mathematica

ER -

Upper bounds on distance measures in K_3,3-free graphs

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this