𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Factorizations of 4-Regular Graphs and Petersen′s Theorem

✍ Scribed by M. Kouider; G. Sabidussi

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
513 KB
Volume
63
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

On the basis of the observation that a 3-regular graph has a perfect matching if and only if its line graph has a triangle-free 2 -factorisation, we show that a connected 4-regular graph has a triangle-free 2 -factorisation, provided it has no more than two cut-vertices belonging to a triangle. This result is equivalent to Petersen's theorem about the existence of perfect matchings in 3-regular graphs. 61995 Academic Press, Inc

📜 SIMILAR VOLUMES

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

Factorizations of regular graphs of high
Factorizations of regular graphs of high degree
✍ A. J. W. Hilton 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

A p-factor of a graph G is a regular spanning subgraph of degree p . For G regular of degree d ( G ) and order 2n, let ( p l , ..., p,) be a partition of d ( G ) , so that p i > 0 ( I S i S r ) and p , i i pr = d(G). If H I . ..., H, are edge-disjoint regular spanning subgraphs of G of degrees p I ,

One-factorizations of complete graphs wi
One-factorizations of complete graphs with vertex-regular automorphism groups
✍ Arrigo Bonisoli; Domenico Labbate 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract We consider one‐factorizations of __K__~2__n__~ possessing an automorphism group acting regularly (sharply transitively) on vertices. We present some upper bounds on the number of one‐factors which are fixed by the group; further information is obtained when equality holds in these boun