@article {LeGrow2016, title = {Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs}, journal = {Designs, Codes and Cryptography}, volume = {80}, number = {3}, year = {2016}, month = {Sep}, pages = {421{\textendash}433}, abstract = {

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 {\textendash}-called blocks{\textendash}-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{\textquoteright}\)\ 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{\textendash}-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 .

}, issn = {1573-7586}, doi = {10.1007/s10623-015-0110-6}, url = {https://doi.org/10.1007/s10623-015-0110-6}, author = {LeGrow, Jason T. and Pike, David A. and Poulin, Jonathan} }