𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the decomposition of Kn into complete m-partite graphs

✍ Scribed by Qingxue Huang

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
195 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Graham and Pollak [3] proved that n −1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges of K~n~ can be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show that for “almost all n,” ⌊ (n + m −3)/(m −1) ⌋ is the minimum number of edge‐disjoint complete m‐partite subgraphs in a decomposition of K~n~.

📜 SIMILAR VOLUMES

On the decomposition of kn into complete
On the decomposition of kn into complete bipartite graphs
✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.

Sharp bounds for decompositions of graph
Sharp bounds for decompositions of graphs into completer-partite subgraphs
✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w

On the asymptotic value of the choice nu
On the asymptotic value of the choice number of complete multi-partite graphs
✍ Nurit Gazit; Michael Krivelevich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We calculate the asymptotic value of the choice number of complete multi‐partite graphs, given certain limitations on the relation between the sizes of the different sides. In the bipartite case, we prove that if __n__~0~ ≤ __n__~1~ and log__n__~0~ ≫ loglog__n__~1~, then $ch(K\_{n\_{0},

On perfect Γ-decompositions of the compl
On perfect Γ-decompositions of the complete graph
✍ Marco Buratti; Anita Pasotti 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract Generalizing the well‐known concept of an __i__‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph __K__~__v__~ to be __i‐perfect__ if for every edge [__x__, __y__] of __K__~__v__~ there is exactly one bl

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 triangular embeddings o
On the number of triangular embeddings of complete graphs and complete tripartite graphs
✍ M. J. Grannell; M. Knor 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract We prove that for every prime number __p__ and odd __m__>1, as __s__→∞, there are at least __w__ face 2‐colorable triangular embeddings of __K__~__w, w, w__~, where __w__ = __m__·__p__^__s__^. For both orientable and nonorientable embeddings, this result implies that for infinitely many