✦ LIBER ✦

Girth, minimum degree, and circumference

✍ Scribed by M. N. Ellingham; D. K. Menser

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 129 KB
Volume: 34
Category: Article
ISSN: 0364-9024
DOI: 10.1002/1097-0118(200007)34:3<221::aid-jgt3>3.0.co;2-t

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Circumference and girth

✍ Cun-Quan Zhang 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB

Let G be 2-connected graph with girth g and minimum degree d. Then each, pair of verticfs of G is joined by a path of length a t least maxi? (dl)g, ( d -?) (g -4) + 2) if g B 4, and the length of a longest cycle of G is at least max{[(d -1) (g -2) + 21, [(2d -3) (g -4) + 41).

Independence, odd girth, and average deg

Independence, odd girth, and average degree

✍ Christian Löwenstein,; Anders Sune Pedersen,; Dieter Rautenbach;; Friedrich Rege 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree a

Graphs of Prescribed Girth and Bi-Degree

✍ Z. Furedi; F. Lazebnik; A. Seress; V.A. Ustimenko; A.J. Woldar 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 426 KB

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

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