Twofold triple systems with cyclic 2-intersecting Gray codes


Abstract in English

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.

Download