Simple separable graphs
Ralph H. V.A. Johnson · Pacific Journal of Mathematics · 1975
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.144 R. H. JOHNSON THEOREM 1.1.If graphs G and H have the same degree sequence then there exists a finite number of transfers ίj, , t r such that 2. The results of this section are essential but easy.For the sake of completeness all proofs are given -at the risk of being wearisome.PROPOSITION 2.1.A graph G is simple if and only if for each transfer t of G we have G = tG.Proof This follows directly from 1.1.PROPOSITION 2.2.A graph G is simple if and only if G c (the complement of G) is simple.Proof.First note that if / is an isomorphism of graphs G and H, then / is also an isomorphism of G c and H c .Let G be simple and let H' belong to the same sequence as G c .Then (H f ) c belongs to the same sequence as G does so that G = (H') C .Hence by the aboveIf S is a sequence, | S | denotes the number of realizations of S.PROPOSITION 2.3.S =(dι, \d p ) is a graphical sequence if and only if S' = (p -1 -d p , % p -\-d x ) is.Moreover, \S\ = \S'\.