Premium
On the decomposition of K n into complete m ‐partite graphs
Author(s) -
Huang Qingxue
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150102
Subject(s) - combinatorics , mathematics , bipartite graph , disjoint sets , algebraic number , decomposition , enhanced data rates for gsm evolution , discrete mathematics , graph , computer science , mathematical analysis , ecology , telecommunications , biology
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 .