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

Citation:

LeGrow, J. T. , Pike, D. A. , & Poulin, J. . (2016). Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs. Designs, Codes and Cryptography, 80(3), 421–433. Sep. doi:10.1007/s10623-015-0110-6

Date Published:

Sep

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 –-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 .

Notes:

Publisher's Version

Last updated on 08/10/2017