✦ LIBER ✦

Average distance, minimum degree, and spanning trees

✍ Scribed by Dankelmann, Peter; Entringer, Roger

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 218 KB
Volume: 33
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200001)33:1<1::aid-jgt1>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

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 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 3 -free graphs, C 4 -free graphs, and for graphs of given girth.

📜 SIMILAR VOLUMES

Mean distance and minimum degree

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

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

Minimum Spanning Trees and Types of Diss

Minimum Spanning Trees and Types of Dissimilarities

✍ Bruno Leclerc 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 295 KB

Lower and upper bounds for the degree-co

Lower and upper bounds for the degree-constrained minimum spanning tree problem

✍ Alexandre Salles da Cunha; Abilio Lucena 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

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

Toughness, minimum degree, and spanning

Toughness, minimum degree, and spanning cubic subgraphs

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

The electronic version has been replaced with the correct figures; the corrected print version follows. The article originally posted in Wiley InterScience is available from the publisher should anyone require access to it. We regret any inconvenience this may have caused.

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