Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs

A cycle \(\mathscr {C}\) in a graph \(G\) is called extendable if there is another cycle in \(G\) which contains all the vertices of \(\mathscr {C}\) and exactly one other vertex. A graph \(G\) is cycle extendable if all its non-Hamilton cycles are extendable. A balanced incomplete block design with parameters \(v\), \(k\), and \(\lambda \), written BIBD\( (v, k, \lambda ) \), is a pair \(\mathscr {D}= (V, \mathscr {B})\) of sets, where \(V\) is a set of \(v\) elements and \(\mathscr {B}\) is a set of \(k\)-subsets of \(V\)—called blocks—such that each pair of elements of \(V\) appears in exactly \(\lambda \) blocks in \(\mathscr {B}\). The 0-block-intersection graph of a design \(\mathscr {D}= (V, \mathscr {B})\) is the graph \(\overline{G}_\mathscr {D}\) whose vertex set is \(\mathscr {B}\) and in which two blocks are adjacent if and only if they do not intersect. An \(A_1'\) cyclic ordering of a BIBD\( (v, k, \lambda )\) is a listing of the elements of its block set such that consecutive blocks do not intersect and the last block does not intersect the first—such an ordering corresponds to a Hamilton cycle in the 0-block-intersection graph of the design and to a 0-intersecting Gray code for the design, and vice versa. In this paper we demonstrate that if \(\overline{G}_\mathscr {D}\) is the 0-block-intersection graph of \(\mathscr {D}\), a BIBD\( (v, k, \lambda )\), then \(\overline{G}_\mathscr {D}\) is Hamiltonian if \(\lambda =1\) and \(v > \left( \frac{1+\sqrt{5}}{2}\right) k^2+k\), and cycle extendable if \(v > 2k^2+1\). We also present a polynomial-time algorithm for finding cycles of any length in the 0-block-intersection graph of a BIBD\( (v, k, \lambda ) \) with \(v > (2+\sqrt{3})k^2+1\) if \(\lambda =1\) or \(v > 5k^2+1\) if \(\lambda \geqslant 2\).