✦ LIBER ✦

Regular Graphs, Eigenvalues and Regular Factors

✍ Scribed by Hongliang Lu

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 97 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20581

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all values of k such that every r‐regular graph with the third largest eigenvalue at most has a k‐factor.

📜 SIMILAR VOLUMES

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

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.

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.

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 +

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

Isomorphic factorizations VII. Regular g

Isomorphic factorizations VII. Regular graphs and tournaments

✍ N. C. Wormald 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB