✦ LIBER ✦

Mean distance and minimum degree

✍ Scribed by Kouider, Mekkia; Winkler, Peter

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 80 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199705)25:1<95::aid-jgt7>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that in a graph of order n and minimum degree d, the mean distance µ must satisfy

This asymptotically confirms, and improves, a conjecture of the computer program GRAFFITI. The result is close to optimal; examples show that for any d, µ may be larger than n/(d + 1).

📜 SIMILAR VOLUMES

Erratum: Mean distance and minimum degre

Erratum: Mean distance and minimum degree

✍ Kouider, Mekkia; Winkler, Peter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

95-99 mistakenly attributes the computer program GRAFFITI to Fajtlowitz and Waller, instead of just Fajtlowitz. (Our apologies to Siemion Fajtlowitz.) Note also that one of the ''flaws'' we note for Conjecture 62 (that it was made for graphs regular of degree d, vice graphs of minimum degree d) was

Average distance, minimum degree, and sp

Average distance, minimum degree, and spanning trees

✍ Dankelmann, Peter; Entringer, Roger 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 218 KB

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) = ( n 2 ) -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

Girth, minimum degree, and circumference

✍ M. N. Ellingham; D. K. Menser 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

Edge-vulnerability and mean distance

✍ Odile Favaron; Mekkia Kouider; Maryvonne Mahéo 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB

On minimum Hellinger distance estimation

✍ Jingjing Wu; Rohana J. Karunamuni 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 French ⚖ 400 KB

Toughness, minimum degree, and spanning

Toughness, minimum degree, and spanning cubic subgraphs

✍ D. Bauer; T. Niessen; E. Schmeichel 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

## Abstract Degree conditions on the vertices of a __t__‐tough graph __G__ (1 ≤ t < 3) are presented which ensure the existence of a spanning cubic subgraph in __G__. These conditions are best possible to within a small additive constant for every fixed rational __t__ ∈[1,4/3)∪[2,8/3). © 2003 Wiley