Files in this item



application/pdf8218574.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Distance-Regular Graphs and Generalizations
Author(s):Terwilliger, Paul M.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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.
Issue Date:1982
Description:115 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1982.
Other Identifier(s):(UMI)AAI8218574
Date Available in IDEALS:2014-12-16
Date Deposited:1982

This item appears in the following Collection(s)

Item Statistics