𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular factors of regular graphs

✍ Scribed by B. Bollobás; Akira Saito; N. C. Wormald

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
242 KB
Volume
9
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a 2-factor and a cubic 2-edge-connected graph has a I-factor. Almost fifty years later, Babler [ l ] showed that a regular

📜 SIMILAR VOLUMES

Almost-regular factorization of graphs
Almost-regular factorization of graphs
✍ Jin Akiyama; Mikio Kano 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

For integers a and b, 0 s a s b, an [a,bl-graph G satisfies a s deg(x,G) s b for every vertex x of G, and an [a.bl-factor is a spanning subgraph its edges can be decomposed into [a,bl-factors. When both k and tare positive integers and s is a nonnegative integer, w e prove that every [(12k + 2)t +

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

A degree condition for the existence of
A degree condition for the existence of regular factors inK1,n-free graphs
✍ Ota, Katsuhiro; Tokuda, Taro 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 2 views

A graph is called K1,.-free if it contains no K l , n as an induced subgraph. Let n ( r 3), r be integers (if r is odd, r 2 n -1). We prove that every Kl,,-free connected graph G with rlV(G)I even has an r-factor if its minimum degree is at least This degree condition is sharp.