Citation:
Date Published:
SepAbstract:
A cycle C in a graph G is called extendable if there is another cycle in G which contains all the vertices of 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 D=(V,B) of sets, where V is a set of v elements and B is a set of k -subsets of V –-called blocks–-such that each pair of elements of V appears in exactly λ blocks in B. The 0-block-intersection graph of a design D=(V,B) is the graph ¯GD whose vertex set is 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 ¯GD is the 0-block-intersection graph of D , a BIBD(v,k,λ) , then ¯GD is Hamiltonian if λ = 1 and v>1+√52k2+k, and cycle extendable if 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,λ) with v>(2+√3)k2+1 if λ = 1 or v>5k2+1 λ ⩾ 2 .