✦ LIBER ✦

[a,b]-factorizations of graphs

✍ Scribed by Cai Mao-Cheng

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let a and b be integers with b ⩾ a ⩾ 0. A graph G is called an [a,b]‐graph if a ⩽ d~G~(v) ⩽ b for each vertex v ∈ V(G), and an [a,b]‐factor of a graph G is a spanning [a,b]‐subgraph of G. A graph is [a,b]‐factorable if its edges can be decomposed into [a,b]‐factors. The purpose of this paper is to prove the following three theorems: (i) if 1 ⩽ b ⩽ 2__a__, every [(12__a__ + 2)m + 2__an__,(12__b__ + 4)m + 2__bn__]‐graph is [2__a__, 2__b__ + 1]‐factorable; (ii) if b ⩽ 2__a__ −1, every [(12__a__ −4)m + 2__an__, (12__b__ −2)m + 2__bn__]‐graph is [2__a__ −1,2__b__]‐factorable; and (iii) if b ⩽ 2__a__ −1, every [(6__a__ −2)m + 2__an__, (6__b__ + 2)m + 2__bn__]‐graph is [2__a__ −1,2__b__ + 1]‐factorable, where m and n are nonnegative integers. They generalize some [a,b]‐factorization results of Akiyama and Kano [3], Kano [6], and Era [5].

📜 SIMILAR VOLUMES

Orthogonal factorizations of graphs

✍ Haodi Feng; Guizhen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph with vertex set __V__(__G__) and edge set __E__(__G__). Let __k__~1~, __k__~2~,…,__k__~m~ be positive integers. It is proved in this study that every [0,__k__~1~+…+__k__~__m__~−__m__+1]‐graph __G__ has a [0, __k__~i~]~1~^__m__^‐factorization orthogonal to any given

[a, b]-factors of graphs

✍ Mikio Kano; Akira Saito 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 303 KB

For integers a and b such that 0~ Q < b, a graph G is called an [a, b]-graph if a s c&(x) s b for every vertex x of G and a factor F of a graph is called an [a, b]-factor if a s d&) i b for every vertex x of F. We prove the following theorems. Let 0 c 1 d k s r, 0 s s, 0 G u and 1 d t. Then an [r, r

[a,b]-factorization of a graph

✍ Mikio Kano 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 781 KB

Let a and b be integers such that 0 s a s b. Then a graph G is called an [a,bl-graph if a 6 dG(x) s b for every x E V(G), and an [a,b]-factor of a graph is defined to be its spanning subgraph F such that a d dF(x) d b for every vertex x, where dG(x) and dJx) denote the degrees of x in G and F, respe

Cube factorizations of complete graphs

✍ Peter Adams; Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract A cube factorization of the complete graph on __n__ vertices, __K~n~__, is a 3‐factorization of __K~n~__ in which the components of each factor are cubes. We show that there exists a cube factorization of __K~n~__ if and only if __n__ ≡ 16 (mod 24), thus providing a new family of unifor

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

On isomorphic factorizations of circulan

On isomorphic factorizations of circulant graphs

✍ Brian Alspach; Danny Dyer; Donald L. Kreher 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract We investigate the conjecture that every circulant graph __X__ admits a __k__‐isofactorization for every __k__ dividing |__E__(__X__)|. We obtain partial results with an emphasis on small values of __k__. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006