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 $l, written BIBD$ (v, k, \lambda (v,k,l) 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 $l 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,l) 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,l) then \overline{G}_\mathscr {D}$G D is Hamiltonian if \lambda =1$$l=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,l) with $v (2+\sqrt{3})k^2+1$$v>(2+3)k2+1 if \lambda =1$$l=1 or $v 5k^2+1$$v>5k2+1 if \lambda \geqslant 2$$l2.
Des. Codes Cryptogr.