Twofold triple systems with cyclic 2-intersecting Gray codes

Abstract

Given a combinatorial design $\mathcal{D}$ with block set $\mathcal{B}$, the block-intersection graph (BIG) of $\mathcal{D}$ is the graph that has $\mathcal{B}$ as its vertex set, where two vertices $B_1\in \mathcal{B}$ and $B_2\in \mathcal{B}$ are adjacent if and only if $|B_1\cap B_2|>0$. The $i$-block-intersection graph ($i$-BIG) of $\mathcal{D}$ is the graph that has $\mathcal{B}$ as its vertex set, where two vertices $B_1\in \mathcal{B}$ and $B_2\in \mathcal{B}$ are adjacent if and only if $|B_1\cap B_2|=i$. In this paper several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian $2$-BIGs and result in larger TTSs that also have Hamiltonian $2$-BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian $2$-BIGs (equivalently TTSs with cyclic $2$-intersecting Gray codes) as well as the complete spectrum for TTSs with $2$-BIGs that have Hamilton paths (i.e., for TTSs with $2$-intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel clasess in arbitrary TTSs, and then construct larger TTSs with both cyclic $2$-intersecting Gray codes and parallel classes.