| Summary: | Thesis (M.Sc.)--Memorial University of Newfoundland, 2010. Mathematics and Statistics Includes bibliographical references (leaves 42-44) Given a balanced incomplete block design [Special characters omitted.] = (V , [Special characters omitted.] ) with block set [Special characters omitted.] , its traditional block-intersection graph G ([Special characters omitted.] ) is the graph having vertex set [Special characters omitted.] such that two vertices β1 , β2 ∈ [Special characters omitted.] are adjacent if and only if β1 ∩ β2 ≠ [Special characters omitted.] . The I-block-intersection graph of a design [Special characters omitted.] = (V , [Special characters omitted.] ), denoted by GI ([Special characters omitted.] ), is the graph having vertex set [Special characters omitted.] such that two vertices β1 , β2 ∈ [Special characters omitted.] are adjacent if and only if |β1 ∩ β 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 ([Special characters 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) (υ, 4, λ)-BIBD with arbitrary λ is Hamiltonian for υ ≥ 11, (2) (υ, 5, λ)-BIBD with arbitrary λ is Hamiltonian for υ ≥ 57, (3) (υ, 6, λ)-BIBD with arbitrary λ is Hamiltonian for υ ≥ 167. We then extend the idea of Horák, Pike and Raines [11], and prove that the 1-block-intersection graph of any (υ, 4, λ)-BIBD with arbitrary λ is Hamiltonian for υ ≥ 136. Finally we end with some open problems related to extensions of work done in this thesis.
|
|---|