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

A cycle $$\mathscr {C}$$C in a graph $$G$$G is called extendable if there is another cycle in $$G$$G which contains all the vertices of $$\mathscr {C}$$C and exactly one other vertex. A graph $$G$$G is cycle extendable if all its non-Hamilton cycles are extendable. A balanced incomplete block design with parameters $$v$$v, $$k$$k, and $$\lambda $$?, written BIBD$$ (v, k, \lambda ) $$(v,k,?), is a pair $$\mathscr {D}= (V, \mathscr {B})$$D=(V,B) of sets, where $$V$$V is a set of $$v$$v elements and $$\mathscr {B}$$B is a set of $$k$$k-subsets of $$V$$V--called blocks--such that each pair of elements of $$V$$V appears in exactly $$\lambda $$? blocks in $$\mathscr {B}$$B. The 0-block-intersection graph of a design $$\mathscr {D}= (V, \mathscr {B})$$D=(V,B) is the graph $$\overline{G}_\mathscr {D}$$G¯D whose vertex set is $$\mathscr {B}$$B and in which two blocks are adjacent if and only if they do not intersect. An $$A_1'$$A1? cyclic ordering of a BIBD$$ (v, k, \lambda )$$(v,k,?) 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}$$G¯D is the 0-block-intersection graph of $$\mathscr {D}$$D, a BIBD$$ (v, k, \lambda )$$(v,k,?), then $$\overline{G}_\mathscr {D}$$G¯D is Hamiltonian if $$\lambda =1$$?=1 and $$v > \left( \frac{1+\sqrt{5}}{2}\right) k^2+k$$v>1+52k2+k, and cycle extendable if $$v > 2k^2+1$$v>2k2+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 ) $$(v,k,?) with $$v > (2+\sqrt{3})k^2+1$$v>(2+3)k2+1 if $$\lambda =1$$?=1 or $$v > 5k^2+1$$v>5k2+1 if $$\lambda \geqslant 2$$??2.