2002
Fiala, Nick Christopher
Seress, Akos
This dissertation consists of three chapters, each one based upon papers by the
author. Chapter 1 deals with a conjecture in combinatorial design theory and
extremal set theory known as the λ-design conjecture. A λ-design
on v points is a set of v subsets (blocks) of
a v-set (points) such that any two distinct blocks meet in
exactly λ points and not all of the blocks have the same size. Ryser's
and Woodall's λ-design conjecture states that all λ-designs can be
obtained from symmetric designs by a complementation procedure. We prove the
conjecture is true when v = 6p + 1, where
p is prime, and when v = 8 q
+ 1, where q ≡ 1 or 7 (mod 8) is prime. Chapter 2 deals
with the determination of all strongly regular graphs (srg's) with chromatic
number 5. A srg is a finite simple regular graph, not complete or edgeless, such
that the number of common neighbors of any two distinct vertices depends only
upon whether or not they are adjacent. The chromatic number of a graph is the
fewest number of colors that are required to color its vertices such that
adjacent vertices always receive different colors. Haemers determined all srg's
with chromatic number 3 or 4. We use eigenvalue techniques and computer
enumerations to begin the determination of all srg's with chromatic number 5. We
show that there are at most 43 possible sets of parameters for such a graph. We
deal completely with 32 sets and obtain a partial result for another set.
Chapter 3 deals with a generalization of srg's the author calls strongly regular
vertices (srv's) and partially strongly regular graphs (psrg's). A srv in a
finite simple graph is such that the number of common neighbors it has with any
other vertex depends only upon whether or not they are adjacent. A psrg is a
regular graph with at least one srv. We prove some basic properties of srv's and
psrg's, provide several constructions of psrg's, determine all psrg's on at most
10 vertices, and make several conjectures regarding psrg's.