Covering cliques with spanning bicliques
Andr� K�ndgen · Journal of Graph Theory · 1998
The edges of the complete graph on n vertices can be covered by ⌈lg n⌉ spanning complete bipartite subgraphs. However, the sum of the number of edges in these subgraphs is roughly (n2/4)lg n, while a cover consisting of n − 1 spanning stars uses only (n − 1)2 edges. We will show that the covering by spanning stars has the smallest total number of edges among all coverings of the clique by spanning complete bipartite subgraphs, except when n is 4 or 8. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 223–227, 1998