Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

✍ Scribed by Dan Pritikin

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 195 KB
• Volume: 10
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190100208

✦ Synopsis

Graham and Pollak 121 proved that n -1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K,, decompose. Tverberg 161, using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcsledges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee 14). We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.

K(1, 1). (The reader may consult [3] for any undefined terminology.) Graham