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

Notes:

Publisher's Version

Last updated on 08/10/2017