Existence of incomplete canonical Kirkman covering designs (Q2297710): Difference between revisions

A covering of order \(v\) is a pair \((X,\mathcal{B})\) where \(X\) is a \(v\)-set and \(\mathcal{B}\) is a collection of subsets (blocks) such that each \(2\)-subset of \(X\) is contained in at least one block of \(\mathcal{B}\). The excess of \((X,\mathcal{B})\) is a graph \((X,E)\) where \(\{x,y\} \in E\) if and only if \(\{x,y\}\) is contained in at least two blocks of \(\mathcal{B}\). A covering is called resolvable if the block set \(\mathcal{B}\) can be partitioned into parallel classes such that each element of \(X\) is contained in precisely one block of each class. If \(v\equiv 4\pmod{6}\) and \(v\geq 4\), a canonical Kirkman covering of order \(v\), denoted by CKCD\((v)\), is a resolvable covering with \((v-4)/2 + 1\) parallel classes such that \((i)\) each parallel class consists of \((v-4)/3\) triples and a single block of size \(4\); and \((ii)\) the excess consists of a union of \((v-4)/2\) vertex disjoint edges. The existence of canonical Kirkman coverings has been completely settled. In this paper, the authors investigate the existence of incomplete canonical Kirkman coverings. An ICKCD\((u,v)\) is a canonical Kirkman covering of order \(u\) which is missing as a subdesign a canonical Kirkman covering of order \(v\). They show that for \(u\geq 3v+4\) there exists an ICKCD\((u,v)\) with the exception of \((u,v)=(16,4)\) and possible exceptions when \(v > 76\), \(v\equiv 4 \pmod{12}\) and \(u\in \{3v+4,3v+10\}\). The main recursive constructions use group divisible designs with block size \(4\) and Kirkman frames. The paper includes direct constructions for several cases and quite a bit of computational work.