✦ LIBER ✦

1-Factorizations of random regular graphs

✍ Scribed by M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 204 KB
Volume: 10
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199705)10:3<305::aid-rsa1>3.0.co;2-#

No coin nor oath required. For personal study only.

✦ Synopsis

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 almost sure in one sequence of spaces are almost sure in the other, and vice versa. The corresponding statement is also shown for bipartite graphs, and from this it is shown that a random r-regular simple digraph is almost surely strongly Ž .

📜 SIMILAR VOLUMES

2-factors in random regular graphs

✍ Robalewska, Hanna D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 2 views

In this paper the expectation and variance of the number of 2-factors in random r-regular graphs for any fixed r 2 3 is analyzed and the asymptotic distribution of this variable is determined.

Fixed Points of Automorphisms of Graphs

Fixed Points of Automorphisms of Graphs with 1 – Factorizations

✍ Ulrike Baumann 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

P4-decompositions of regular graphs

✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

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 degr

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

Factorizations of complete multipartite

Factorizations of complete multipartite graphs into generalized cubes

✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 1 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite

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.