Cycle Extensions in BIBD Block‐Intersection Graphs

A cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non‐Hamilton cycle in the graph is extendable. A balanced incomplete block design, BIBD ( v , k , λ ) , consists of a set V of v elements and a block set B of k ‐subsets of V such that each 2‐subset of V occurs in exactly λ of the blocks of B . The block‐intersection graph of a design D = ( V , B ) is the graph G D having B as its vertex set and such that two vertices of G D are adjacent if and only if their corresponding blocks have nonempty intersection. In this paper, we prove that the block‐intersection graph of any BIBD ( v , k , λ ) is cycle extendable. Furthermore, we present a polynomial time algorithm for constructing cycles of all possible lengths in a block‐intersection graph.