Citation:
Date Published:
SepAbstract:
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 λ , written BIBD(v,k,λ) , 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 λ 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,λ) 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,λ) , then \(\overline{G}_\mathscr{D}\) is Hamiltonian if λ = 1 and \(v > \frac{1+\sqrt{5}}{2}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,λ) with \(v > (2+\sqrt{3})k^2+1\) if λ = 1 or \(v>5k^2+1\) λ ⩾ 2 .