Design Theory, 2nd Edition

4

Maximum Packings and Minimum Coverings

 

4.1 The general problem

As we are well aware by now, it is impossible to construct a Steiner triple system of order υ when υ ≢ 1 or 3 (mod 6) . A quite natural question to ask then, is just how “close” can we come to constructing a triple system for υ ≡ 0 , 2, 4, or 5 (mod 6). Obviously, in order to attack this problem we must first define what we mean by”close”. When υ ≡ 5 (mod6), in Section 1.4 we defined”close” to mean one block of size 5 and the remaining blocks of size 3. In what follows we will define “close” in two different ways. So, here goes!

The following two definitions are best described using graph theoretic vernacular. A packing of the complete graph K υ