Vol. 56, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Simple separable graphs

R. H. Johnson

Vol. 56 (1975), No. 1, 143–158

The relation between the structure of a graph and the degrees of its vertices is a problem that has long occupied graph theorists in one form or another. If the degrees of the vertices of a graph are arranged in nonincreasing order the sequence obtained is the degree sequence of the graph. Thus the above problem is often formulated as “how does the degree sequence affect the structure of the graph?” One approach is to discover which graphs are determined up to isomorphism by their degree sequence. Following Harary, these latter graphs and their degree sequences are called simple. In simple graphs the effect of the degree sequence on structure is, in a good sense, isolated. In this paper all simple graphs which are not blocks are determined.

Mathematical Subject Classification 2000
Primary: 05C99
Received: 28 September 1973
Revised: 6 May 1974
Published: 1 January 1975
R. H. Johnson