Abstract
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 |
Pages | 15-20 |
Number of pages | 6 |
ISBN (Electronic) | 9781461472544 |
ISBN (Print) | 9781461472537 |
DOIs | |
State | Published - Jan 1 2013 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics