✦ LIBER ✦

P4-decompositions of regular graphs

✍ Scribed by Heinrich, Katherine; Liu, Jiping; Yu, Minli

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 246 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199906)31:2<135::aid-jgt6>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle-free Eulerian tour.

📜 SIMILAR VOLUMES

r-Regular, r-connected decompositions of

r-Regular, r-connected decompositions of complete graphs

✍ H. Fleischner; W. R. Johnstone; A. J. W. Hilton 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

If rjn À 1 and rn is even, then K n can be expressed as the union of t nÀ1 r edgedisjoint isomorphic r-regular r-connected factors.

From regular boundary graphs to antipoda

From regular boundary graphs to antipodal distance-regular graphs

✍ Fiol, M. A.; Garriga, E.; Yebra, J. L. A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

Let Γ be a regular graph with n vertices, diameter D, and d + 1 In a previous paper, the authors showed that if P (λ) > n -1, then D ≤ d -1, where P is the polynomial of degree d-1 which takes alternating values ±1 at λ 1 , . . . , λ d . The graphs satisfying P (λ) = n -1, called boundary graphs, h

Tree decomposition of graphs

✍ Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

with ␦ G G V r2 q 10 h V log V , and h y 1 divides E , then there is a decomposition of the edges of G into copies of H. This result is asymptotically the best possible for all trees with at least three vertices.

Deza graphs: A generalization of strongl

Deza graphs: A generalization of strongly regular graph

✍ M. Erickson; S. Fernando; W. H. Haemers; D. Hardy; J. Hemmeter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

1-Factorizations of random regular graph

1-Factorizations of random regular graphs

✍ M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 2 views

It is shown that for each r G 3, a random r-regular graph on 2 n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2 n vertices, as n ª ϱ. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almo

Resistance distance in regular graphs

✍ I. Lukovits; S. Nikolić; N. Trinajstić 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB 👁 2 views

This report considers the resistance distance as a recently proposed new ## Ž . intrinsic metric on molecular graphs, and in particular, the sum R over resistance distances between all pairs of vertices is considered as a graph invariant. It has been vertices and K denotes a complete graph contai