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

Jesso, Andrew Thomas. (2010) The Hamiltonicity of block-intersection graphs of balanced incomplete block designs. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (2MB)

Abstract

Given a balanced incomplete block design [Special character omitted] = (V, [Special character omitted]) with block set [Special character omitted], its traditional block-intersection graph G([Special character omitted]) is the graph having vertex set [Special character omitted] such that two vertices β₁,β₂ ∈ [Special character omitted] are adjacent if and only if β₁ ⋂ β₂ ≠ 0. The I-block-intersection graph of a design [Special character omitted] = (V, [Special character omitted]), denoted by GI ([Special character omitted.), is the graph having vertex set [Special character omitted] such that two vertices β₁,β₂ ∈ [Special character omitted] are adjacent if and only if |β₁ ⋂ β₂| ∈ 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 Gᵢ ([Special character omitted]), where i is the sole element of I. -- 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 Horák 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]. -- 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) (v, 4, λ)-BIBD with arbitrary λ is Hamiltonian for v ≥ 11, -- (2) (v, 5, λ)-BIBD with arbitrary λ is Hamiltonian for v ≥ 57, -- (3) (v, 6, λ)-BIBD with arbitrary λ is Hamiltonian for v ≥ 167. -- We then extend the idea of Horák, Pike and Raines [11], and prove that the 1-block-intersection graph of any (v, 4, λ)-BIBD with arbitrary λ is Hamiltonian for v ≥ 136. Finally we end with some open problems related to extensions of work done in this thesis.

Actions (login required)

View Item