This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/71204
Description
Title
Distance-Regular Graphs and Generalizations
Author(s)
Terwilliger, Paul M.
Issue Date
1982
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Mathematics
Abstract
A distance-transitive graph (GAMMA) is an undirected, locally finite graph where for any vertices u,v,x,y, (PAR-DIFF)(u,v) = (PAR-DIFF)(x,y) implies (sigma)u = x and (sigma)v = y for some automorphism (sigma) of (GAMMA). Distance-transitive graphs have certain combinatorial properties, which can be studied independently; a graph with these properties is called distance-regular.
We deal first with distance-regular graphs with girth 3 and 4. We show any such graph which contains a cycle (v(,1),v(,2),v(,3),v(,4),v(,1)) where (PAR-DIFF)(v(,1),v(,3)) = (PAR-DIFF)(v(,2),v(,4)) = 2 is finite with diameter d bounded by its valency k. Next we obtain new "feasibility conditions" that the intersection numbers of arbitrary distance-regular graphs with girth 3 or 4 must satisfy. We use these conditions to generate the intersection array of certain distance-regular graphs from their valency and three other parameters.
We then study distance-regular graphs with arbitrary girth and extend the ideas used in the girth 3 or 4 case to obtain a bound on the diameter of a class of distance-regular graphs, including all those with even girth. We then introduce a generalization of a distance-regular graph called a (s,c,a,k)-graph, which possesses enough of the local structure of a distance-regular graph to enable us to find bounds on their diameters in some cases. Finally we obtain lower bounds on the eigenvalue multiplicities for distance-regular graphs in terms of their valence and girth, yielding additional feasibility conditions for their intersection arrays.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.