Dissertation

Graph Isomorphisms

This dissertation deals with some basic proper ties of finite graphs having no loops and no parallel lines. In particular it is concerned with properties which help determine when two graphs are isomorphic and when a map of a graph on itself is an automorphism. Section 1 contains those basic definitions which will be used throughout the text. Section 2 introduces the concepts of degree set, degree frequency, and distinguished points. It is proven there that graphs exist having the maximum and minimum numbers of possible distinguished points, and that any degree-preserving map on a graph having a maximum number of distinguished points is an automorphism. It is also shown that there exist regular graphs of all degrees, subject only to the condition that there be an even number of points having an odd degree. Section 3 is concerned with conditions imposed on a graph by the frequencies with which degrees are assumed in a graph, and the relationship of such frequencies to isomorphisms between graphs. The major theorem of this section states that there exist graphs having any frequencies of degrees, subject to the condition that at least two points have the same degree. A constructive method is given which produces graphs having given degree frequencies. A characterization is given for graphs having the property that all degree preserving maps are automorphisms. Section 4 presents the history of a conjecture concerning a possible inductive method of determining isomorphisms between two graphs. Some new results are given, based on the degree sets of the graphs and the clique types of the graphs. Some possible generalizations of the conjecture are stated. In Section 5 isomorphisms between labeled graphs are discussed. It is shown that two graphs are isomorphic if enough of the induced subgraphs are isomorphic in a unique way. Section 6 deals with line graphs--a type of graph which determines its associated graph up to isomorphism. The historical background of line graphs is given together with the relation of these graphs to the conjecture in Section 4. A method is given for constructing all graphs which have regular line graphs.

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.