✦ LIBER ✦

Factorization of regular multigraphs into regular graphs

✍ Scribed by S. I. El-Zanati; M. J. Plantholt; S. K. Tipnis

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 618 KB
Volume: 19
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190190110

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A regular multigraph with maximum multiplicity r and degree rs cannot always be factored into r s‐regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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 +

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

Regular factors in regular graphs

✍ P. Katerinis 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 473 KB

Katerinis, P., Regular factors in regular graphs, Discrete Mathematics 113 (1993) 269-274. Let G be a k-regular, (k -I)-edge-connected graph with an even number of vertices, and let m be an integer such that 1~ m s k -1. Then the graph obtained by removing any k -m edges of G, has an m-factor.

Regular Graphs, Eigenvalues and Regular

Regular Graphs, Eigenvalues and Regular Factors

✍ Hongliang Lu 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB

## 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.

Regular factors in nearly regular graphs

✍ Jean-Claude Bermond; Michel Las Vergnas 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Decompositions of complete graphs into r

Decompositions of complete graphs into regular bichromatic factors

✍ Anton Kotzig 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 517 KB

The proof of the following theorem is given: A complete graph with n vertkes can he decomposed into r regular bichromatic factors if and only if n is even and greater thl;iirl 4 and there exists $1 natural number k with the properties that k < r anu. ak-l < n 5 Zk.