✦ LIBER ✦

On path factorizations of complete multipartite graphs

✍ Scribed by Min-li Yu

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 523 KB
Volume: 122
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90305-d

No coin nor oath required. For personal study only.

✦ Synopsis

Necessary

conditions for IK(n, r), the complete multipartite graph with r parts of size n in which each edge has multiplicity 1, to have a P,-factorization are nr=O(mod k) and i(r-l)kn=O(mod2(k-1)).

We show that when n=O(modk) or r=O(modk), these two conditions are also sufficient. (This implies that for all prime k the above two conditions are sufficient.) As corollaries, we also show that the necessary conditions are sufficient when r= 2 and r = 3.

📜 SIMILAR VOLUMES

Factorizations of complete multipartite

Factorizations of complete multipartite graphs into generalized cubes

✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite

Nondisconnecting disentanglements of ama

Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs

✍ C. D. Leach; C. A. Rodger 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract In this paper necessary and sufficient conditions are found for an edge‐colored graph __H__ to be the homomorphic image of a 2‐factorization of a complete multipartite graph __G__ in which each 2‐factor of __G__ has the same number of components as its corresponding color class in __H__

On minimum sets of 1-factors covering a

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

✍ David Cariolaro; Hung-Lin Fu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 1 views

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

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

Hamilton decompositions of complete mult

Hamilton decompositions of complete multipartite graphs with any 2-factor leave

✍ C. D. Leach; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB 👁 1 views

## Abstract For __m__ ≥ 1 and __p__ ≥ 2, given a set of integers __s__~1~,…,__s__~__q__~ with $s\_j \geq p+1$ for $1 \leq j \leq q$ and ${\sum \_{j\,=\,1}^q} s\_j = mp$, necessary and sufficient conditions are found for the existence of a hamilton decomposition of the complete __p__‐partite graph $

On the euclidean dimension of a complete

On the euclidean dimension of a complete multipartite graph

✍ Hiroshi Maehara 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 272 KB

The euclidean dimension of a graph G, e(G), is the minimum n such that the vertices of G can be placed in euclidean n-space, R", in such a way that adjacent vertices have distance 1 and nonadjacent vertices have distances other than 1. Let G = K(n,, . , ns+,+J be a complete (s + t + u)-partite graph