Premium
Cycle Extensions in BIBD Block‐Intersection Graphs
Author(s) -
Abueida Atif A.,
Pike David A.
Publication year - 2013
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21328
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , intersection (aeronautics) , intersection graph , discrete mathematics , line graph , aerospace engineering , engineering
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.