The motivating idea behind the thesis is the study of the relationship of the degrees of the vertices of a graph and the structure of a graph.
To each graph (indirected, without multiple edges) one can associate a graphical sequence by arranging the degrees of the vertices in their natural order. Conversely, an arbitrary sequence of numbers is graphical if it is a graphical sequence for some graph.
In the first chapter general properties of graphical sequences are studied. We give conditions under which a sequence can be lengthened or shortened and have the property of being graphical be preserved. The concept of a 'transfer' is introduced to show how all realizations of a graphical sequence can be obtained from a given realization. Also in chapter one we show how graphical sequences can be used to characterize concepts like 'connected', 'block' and 'arbitrarily traceable'.
If a graphical sequence has one 'realization' up to isomorphism then the sequence and the graph are called simple. Since simple graphs are determined up to isomorphism by the degrees of the vertices it is hoped that simple graphs will reveal in some measure the effect of the degree sequence on the structure of a graph.
Thus, in chapter two, we attempt to characterize simple graphs--the central problem of the thesis. Simple trees, simple disconnected graphs, and simple graphs with cut points and no pendant vertices are characterized. (This means that characterizing simple blocks will solve the problem). Probably the most useful result is that a connected, simple graph must be of radius ≤ two and diameter ≤ three
The third chapter is devoted to the problem of counting the number of non-isomorphic realizations of a given graphical sequence. Generating functions are used and several interesting special cases are given. These latter are in turn used to establish certain bounds on the number of realizations for sequences of a given length. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/74705 |
| Date | January 1973 |
| Creators | Johnson, Robert H. |
| Contributors | Mathematics |
| Publisher | Virginia Polytechnic Institute and State University |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Dissertation, Text |
| Format | iii, 77 leaves, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | OCLC# 34218387 |
Page generated in 0.0027 seconds