Abstract
A ‘tight single-change covering design’ (tsccd) is an ordered set of blocks, each block comprising k distinct elements taken from the set S = {1, 2, ..., v}, v > k , with the properties that (i) any two members of S occur together in at least one block, (ii) each block after the first is obtained from the previous block by changing just one element, and (iii) the newly introduced element in any block B after the first has not previously appeared in the same block as any of the other elements from B. Existence results for tsccd’s are reviewed, many examples of tsccd’s with k = 2, 3, and 4 are given, and properties of some tsccd’s are examined. For k = 2, 3, and 4, a tsccd can now be constructed for any value of v that is consistent with known existence results. For k = 4, the least such value is v = 12. Tsccd’s with (v, k) = (12, 4) are partially enumerated, and tsccd’s with (v, k) = (15, 4) and (18, 4) are given. A method is presented for using some of these to construct tsccd’s with k = 4 and v equal to any value from the sequence 12, 13, 15, 16, 18, 19, 21, 22, ... . ‘Row-regular’ and ‘element-regular’ tsccd’s are defined; a particularly remarkable tsccd with (v, k) = (12, 4) is presented that is regular in both senses. No tsccd with k > 4 has yet been found.
Recommended Citation
McSorley, John P., Preece, Donald, Constable, R L., Phillips, Nick, Wallis, Walter, Yucas, Joseph and Zhang, Grant. "Tight Single-Change Covering Designs." Utilitas Mathematica 47 (Jan 1995): 55-84.