The Hamiltonicity of block-intersection graphs of balanced incomplete block designs.

摘要

Given a balanced incomplete block design D = (V, B ) with block set B , its traditional block-intersection graph G( D ) is the graph having vertex set B such that two vertices beta1, beta2 ∈ B are adjacent if and only if beta1 ∩ beta2 ≠ empty . The I-block-intersection graph of a design D = (V, B ), denoted by GI( D ), is the graph having vertex set B such that two vertices beta1, beta2 ∈ B are adjacent if and only if |beta1 ∩ beta 2| ∈ I, where I is a given subset of {1, 2, ..., k}. If |I| = 1 then we will also refer to the I-block-intersection graph as the i-block-intersection graph and will denote it by Gi ( D ), where i is the sole element of I.;In this thesis we will prove several lemmata that deal with the size of independent sets of vertices in block-intersection graphs. Also, we will show that the {1, 2}-block-intersection graph of any (1) (upsilon, 4, lambda)-BIBD with arbitrary lambda is Hamiltonian for upsilon ≥ 11, (2) (upsilon, 5, lambda)-BIBD with arbitrary lambda is Hamiltonian for upsilon ≥ 57, (3) (upsilon, 6, lambda)-BIBD with arbitrary lambda is Hamiltonian for upsilon ≥ 167.;We then extend the idea of Horak, Pike and Raines [11], and prove that the 1-block-intersection graph of any (upsilon, 4, lambda)-BIBD with arbitrary lambda is Hamiltonian for upsilon ≥ 136. Finally we end with some open problems related to extensions of work done in this thesis.;The initial investigation into the cycle properties of block-intersection graphs was said to have been initiated by Ron Graham in 1987. One year later, Graham's question was proved by Peter Horak and Alexander Rosa. Since the posing of Graham's question, many people have looked into several different cycle properties of block-intersection graphs, most of which can be found in [1, 4, 6, 9, 10, 13--15].