✦ LIBER ✦

Regular factors in K1,n free graphs

✍ Scribed by Yoshimi Egawa; Katsuhiro Ota

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 280 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150310

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is said to be K~1,n~‐free, if it contains no K~1,n~ as an induced subgraph. We prove that for n ⩾ 3 and r ⩾ n −1, if G is a K~1,n~‐free graph with minimum degree at least (n^2^/4(n −1))r + (3__n__ −6)/2 + (n −1)/4__r__, then G has an r‐factor (in the case where r is even, the condition r ⩾ n −1 can be dropped).

📜 SIMILAR VOLUMES

Regular factors in K1,3-free graphs

✍ S. A. Choudum; M. S. Paulraj 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract We show that every connected __K__~1,3~‐free graph with minimum degree at least __2k__ contains a __k__‐factor and construct connected __K__~1,3~‐free graphs with minimum degree __k__ + __0__(√__k__) that have no __k__‐factor.

Regular factors of regular graphs

✍ B. Bollobás; Akira Saito; N. C. Wormald 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

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

Counting 1-Factors in Regular Bipartite

Counting 1-Factors in Regular Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 325 KB

We show that any k-regular bipartite graph with 2n vertices has at least \ (k&1) k&1 k k&2 + n perfect matchings (1-factors). Equivalently, this is a lower bound on the permanent of any nonnegative integer n\_n matrix with each row and column sum equal to k. For any k, the base (k&1) k&1 Âk k&2 is l

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.

2-factors in random regular graphs

✍ Robalewska, Hanna D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 3 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.

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