Files in this item
Files  Description  Format 

application/pdf 8422017.pdf (3MB)  (no description provided) 
Description
Title:  Polynomials of the Adjacency Matrix of a Graph (distanceTransitive, DistanceRegular, Orbit) 
Author(s):  Beezer, Robert Arnold 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs which can be generated by a polynomial. Define the ith distance graph, (GAMMA)(,i), as the graph with the same vertex set as (GAMMA) and two vertices are adjacent in (GAMMA)(,i) if and only if they are a distance i apart. If (GAMMA) is a distanceregular graph, then for each i there exists a polynomial of degree i, p(,i)(x), such that p(,i)(A((GAMMA))) = A((GAMMA)(,i)). In fact, it has been shown that this property characterizes distanceregular graphs. With the above situation in mind, we construct the definition of an orbit polynomial graph. A graph is orbit polynomial if certain natural 01 matrices (determined by the automorphism group of the graph) are equal to polynomials of the adjacency matrix of the graph. We obtain many results about the properties of these graphs and their connections with association schemes. We also characterize orbit polynomial graphs with a prime number of vertices and the nonsymmetric trivalent orbit polynomial graphs. We then study the graphs generated from a tree by a polynomial. For a path, all of the possible graphs are determined. A sunset is a path of even length with additional vertices adjacent to the central vertex. We produce a polynomial q(x) which generates a graph from a sunset which happens to be isomorphic to the original sunset. Motivated by this example, we study the situation where r(A((GAMMA))) = A((DELTA)), r(x) (NOT=) x, and (GAMMA) is isomorphic to (DELTA). 
Issue Date:  1984 
Type:  Text 
Description:  112 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1984. 
URI:  http://hdl.handle.net/2142/71218 
Other Identifier(s):  (UMI)AAI8422017 
Date Available in IDEALS:  20141216 
Date Deposited:  1984 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois