On the minimum number of edge‐disjoint complete m ‐partite subgraphs into which K n can be decomposed

Abstract Let α m (n) denote the minimum number of edge‐disjoint complete m ‐partite subgraphs into which K n can be decomposed. In [2] the author proved that when m ≥ 3, if (i) n ≡ m and n ≡ m (mod m −1), or (ii) b ∈ [2, m −1], n ≥ b(m −1) + m − ( b −1), and n ≡ b(m −1) + m − ( b −1) (mod m − 1), then α m ( n ) = ⌊( n + m −3)/( m −1)⌋ (= ⌊( n −1)/( m −1)⌋), and that for every integer n , if K n has an edge‐disjoint complete m ‐partite subgraph decomposition, then α m ( n ) ≥ ⌊( n − 1)/( m − 1)⌋. In this paper we generally discuss the question as to which integers n 's satisfy (or do not) α m ( n ) = ⌊( n −1)/( m −1)⌋. Here we also study the methods to find these integers; the methods are themselves interesting. Our main results are Theorem 2.11, 2.12, and 2.16. Besides, Theorem 2.4 and 2.6 are interesting results too. © 1993 John Wiley & Sons, Inc.