✦ LIBER ✦

On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs

✍ Scribed by D.G. Hoffman; C.A. Rodger

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 503 KB
Volume: 160
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00157-r

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we use Tutte's f-factor theorem and the method of amalgamations to find necessary and sufficient conditions for the existence of a k-factor in the complete multipartite graph K(p(1 ) ..... p(n)), conditions that are reminiscent of the Erd6s-Gallai conditions for the existence of simple graphs with a given degree sequence. We then use this result to investigate the maximum number of edge-disjoint 1-factors in K(p(l) ..... p(n)), settling the problem in the case where this number is greater than 6 -p(2), where p(1 ) ~< p(2) ~ • • • ~< p(n).

📜 SIMILAR VOLUMES

On one-factorizations of the complete gr

On one-factorizations of the complete graph

✍ L Pyber 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 66 KB

Edge-chromatic critical graphs and the e

Edge-chromatic critical graphs and the existence of 1-factors

✍ S. A. Choudum 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract We give examples of edge‐chromatic critical graphs __G__ of the following types: (i) of even order and having no 1‐factor, and (ii) of odd order and having a vertex __v__ of minimum degree such that __G__ − __v__ has no 1‐factor. The first disproves a conjecture of S. Fiorini and R. J.

On the size of graphs with complete-fact

On the size of graphs with complete-factors

✍ Jin Akiyama; Peter Frankl 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 1 views

On the existence of a rainbow 1-factor i

On the existence of a rainbow 1-factor in 1-factorizations of K

✍ S.I. El-Zanati; M.J. Plantholt; P.A. Sissokho; L.E. Spence 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB 👁 1 views

## Abstract Let ${\cal F}$ be a 1‐factorization of the complete uniform hypergraph ${\cal G}={K\_{rn}^{(r)}}$ with $r \geq 2$ and $n\geq 3$. We show that there exists a 1‐factor of ${\cal G}$ whose edges belong to __n__ different 1‐factors in ${\cal F}$. Such a 1‐factor is called a “rainbow” 1‐fact

On the number of irreducible coverings b

On the number of irreducible coverings by edges of complete bipartite graphs

✍ Ioan Tomescu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 102 KB

In this paper it is proved that the exponential generating function of the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite graphs Kp.q equals exp(xe r + ye x -x -y -xy) -t.

New bounds on the edge number of a k-map

New bounds on the edge number of a k-map graph

✍ Zhi-Zhong Chen 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract It is known that for every integer __k__ ≥ 4, each __k__‐map graph with __n__ vertices has at most __kn__ − 2__k__ edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for __k__ = 4, 5. We also show that this bound is not tight for large en