Graphical sequences

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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Mathematics

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1973

Author dc:creator

• Johnson, Robert H.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/10919/74705

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/74705