✦ LIBER ✦

On minimum sets of 1-factors covering a complete multipartite graph

✍ Scribed by David Cariolaro; Hung-Lin Fu

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 132 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20303

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We determine necessary and sufficient conditions for a complete multipartite graph to admit a set of 1‐factors whose union is the whole graph and, when these conditions are satisfied, we determine the minimum size of such a set. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:239‐250, 2008

📜 SIMILAR VOLUMES

A 1-factorization of the line graphs of

A 1-factorization of the line graphs of complete graphs

✍ Brian Alspach 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB 👁 1 views

## Abstract A 1‐factorization is constructed for the line graph of the complete graph __K~n~__ when __n__ is congruent to 0 or 1 modulo 4.

Bounds on chromatic numbers of multiple

Bounds on chromatic numbers of multiple factors of a complete graph

✍ Ján Plesník 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB 👁 1 views

## Abstract Bounds on the sum and product of the chromatic numbers of __n__ factors of a complete graph of order __p__ are shown to exist. The well‐known theorem of Nordhaus and Gaddum solves the problem for __n__ = 2. Strict lower and some upper bounds for any __n__ and strict upper bounds for __n

Some new results on 1-rotational 2-facto

Some new results on 1-rotational 2-factorizations of the complete graph

✍ Tommaso Traetta 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph __K__~2__n__+1~ under the action of a group __G__ of order 2__n__ is that the involutions of __G__ are pairwise conjugate. Is this condition also sufficient? The complete ans

Symmetric Hamilton cycle decompositions

Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor

✍ Richard A. Brualdi; Michael W. Schroeder 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

Let n ≥ 2 be an integer. The complete graph K n with a 1-factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n -F has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor F if and only if n ≡ 2,4 mod 8. We also show that

Decomposition of the complete graph plus

Decomposition of the complete graph plus a 1-factor into cycles of equal length

✍ Mateja Šajna 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB 👁 1 views

## Abstract We determine the necessary and sufficient conditions for the existence of a decomposition of the complete graph of even order with a 1‐factor added into cycles of equal length. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 170–207, 2003; Published online in Wiley InterScience (www

On the number of (r,r+1)- factors in an

On the number of (r,r+1)- factors in an (r,r+1)-factorization of a simple graph

✍ A. J. W. Hilton 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 113 KB 👁 1 views

## Abstract For integers __d__≥0, __s__≥0, a (__d, d__+__s__)‐__graph__ is a graph in which the degrees of all the vertices lie in the set {__d, d__+1, …, __d__+__s__}. For an integer __r__≥0, an (__r, r__+1)‐__factor__ of a graph __G__ is a spanning (__r, r__+1)‐subgraph of __G__. An (__r, r__+1)‐