A bipartite covering of order k of the complete graph Kn on n vertices is a collection of complete bipartite graphs so that every edge of Kn lies in at least 1 and at most k of them. It is shown that the minimum possible number of subgraphs in such a collection is Θ(kn1/k). This extends a result of Graham and Pollak, answers a question of Felzenbaum and Perles, and has some geometric consequences. The proofs combine combinatorial techniques with some simple linear algebraic tools.
|Original language||English (US)|
|Title of host publication||The Mathematics of Paul Erdos II, Second Edition|
|Publisher||Springer New York|
|Number of pages||6|
|State||Published - Jan 1 2013|
All Science Journal Classification (ASJC) codes