Single-change circular covering designs (Q1292863)

A single-change circular covering design based on the set \([v]= \{1,2,3,\dots, v\}\) with block size \(k\) is an ordered collection of \(b\) blocks, \({\mathcal B}= \{B_1,B_2,\dots, B_b\}\), each an unordered subset of \(k\) distinct elements from \([v]\) which obey (1) each block differs from the previous block by a single element, i.e., \(|B_{i-1}\sqcap B_i|= k-1\) for \(i= 2,3,\dots, b\); and the last block, \(B_b\), differs from the first block, \(B_1\), by a single element, i.e., \(|B_b\sqcap B_1|= k-1\); (2) every (unordered) pair \(\{x,y\}\subseteq[v]\), with \(x\neq y\), can be written as \(\{e_i,z\}\), where \(e_i\in B_i\setminus B_{i-1}\) and \(z\in B_i\) for some \(i= 2,3,\dots,b\), or as \(\{e_1, z\}\), where \(e_1\in B_1\setminus B_b\) and \(z\in B_1\). It is said that, for \(i= 1,2,3,\dots, b\), the element \(e_i\) is `introduced' in block \(B_i\), and the pairs \(\{e_i, z\}\), where \(z\in B_i\), are covered by \(B_i\). It is also said that a pair is covered by \({\mathcal B}\) if it is covered by some block in \({\mathcal B}\). A single-change circular covering design is simply a single-change covering design in which `a single-change' is also required between \(B_b\) and \(B_1\). A single-change circular covering design is denoted by scccd, and a scccd based on \([v]\) with block size \(k\) is denoted by \(\text{scccd}(v, k)\), or by \(\text{scccd}(v, k, b)\) if it is to be mentioned that it contains \(b\) blocks. For fixed \(v\) and \(k\), where \(k\geq 2\) and \(v\geq k+1\), \(b^*(v, k)\) denotes the smallest \(b\) for which there exists a \(\text{scccd}(v, k, b)\). A \(\text{scccd}(v,k,b^*(v, k))\) is called minimal. An economical design is one in which each pair except one is covered once, and that exceptional pair is covered twice. This paper minimizes \(b\) for fixed values of \(v\) and \(k\). Some minimal constructions of scccds for arbitrary \(v\) when \(k=2\) or 3, and for some arbitrary \(k\) when \(k+1\leq v\leq 2k\) are presented. Tight designs are those in which each pair is covered exactly once. Start-finish arrays are used to construct tight designs when \(v> 2k\). It is shown that there are two nonisomorphic tight designs with \((v, k)= (9, 4)\) and 12 with \((v, k)= (10, 4)\). Some nonexistence results for tight designs and standardized, element-regular, perfect, and column-regular designs are also constructed.