Bipartite designs

✍ Scribed by D. G. Hoffman; Mark Liatti

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 240 KB
• Volume: 3
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.3180030608

✦ Synopsis

We determine here those quadruples (a, b, c, d) of positive integers for which the edges of the complete bipartite graph K c , d can be partitioned into copies of K n , b .

1. Introduction

A classic problem in design theory is to partition the edges of the complete graph on v vertices ( K , ) into copies of the complete graph on k vertices (Kk). This problem has not been solved in general, see for example [l].

In this article we develop a general solution to a related problem. We find necessary and sufficient conditions for partitioning the edges of the complete bipartite graph, K,,d , into copies of the smaller complete bipartite graph, Ka,b. Main Theorem. Let a , b, c , d be positive integers. Let g = ( a , b ) , the greatest common divisor of a aiid b ; let e , f be integers satisfying ae -b f = g, and let h = ae + b f.

For each lcteger x, let:

Then the edges of the complete bipartite graph, K c , d , can be partitioned into copies of the complete bipartite graph, K a , b , if and only if the following conditions are true: