SELF-COMPLEMENTARY GRAPHS: THEIR STRUCTURAL PROPERTIES AND ADJACENCY MATRICES Thesis for the Degree of PII. D. MICHIGAN STATE UNIVERSITY RICHARD ADDISON. GIBBS i970 {HERIR This is to certify that the thesis entitled SELF-COMPLEMENTARY GRAPHS: THEIR STRUCTURAL PROPERTIES AND ADJACENCY MATRICES presented by Richard Addison Gibbs has been accepted towards fulfillment of the requirements for Ph.D, degree in Mathematics 4 JWa/wd ;I Am Major professor € Date W) O~169 BINDING BY "DAG & SDNS’ ' ‘IWK BINDERY INB. MIRA!" HINDERS ._ ll ABSTRACT SELF-COMPLEMENTARY GRAPHS: THEIR STRUCTURAL PROPERTIES AND ADJACENCY MATRICES BY Richard Addison Gibbs In this thesis we examine some structural properties and adjacency matrices of self-complementary graphs. We first describe a basic algorithm.which will produce all self- complementary graphs, and from which most of the main results are derived. We show that any self-complementary graph con- tains a collection of induced subgraphs, each isomorphic to the "smallest" self—complementary graph,P3. A useful adjacency matrix is introduced and for certain self—complementary graphs we exhibit a decomposition of such matrices which facilitates the calculation of their eigenvalues. Finally, some results are presented concerning the possible degrees of the points of a self-complementary graph. SELF-COMPLEMENTARY GRAPHS: THEIR STRUCTURAL PROPERTIES AND ADJACENCY MATRICES BY Richard Addison Gibbs A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1970 TO SANDI, BONNIE, NANCY, RICHARD JR. or SALLY and THE FOLKS ii ACKNOWLEDGMENTS I am deeply indebted to Professor J. Sutherland Frame for his patience, inspiration and timely suggestions throughout the research and preparation of this thesis. I also wish to thank Professor E. M. Palmer for his encouragement and interest. Special thanks is due to Professor J. J. Seidel who, although he doesn't know it, started it all. iii TABLE OF CONTENTS Page LIST OF TABLES AND FIGURES . . . . . . . . . . . . . . . V INTRODUCTION . . . . . . . . . . . . .’. . . . . . . . . 1 CHAPTER 1. REVIEW OF THE LITERATURE . . . . . . . . . . . . . 2 2. DEFINITIONS AND NOTATIONS . . . . . . . . . . . . 3 3. THE CONSTRUCTION ALGORITHM . . . . . . . . . . . . 8 4. THE DECOMPOSITION THEOREM . . . . . . . . . . . 21 5.ADJACENCYMATRICES............... 31 6. TYPE-SEQUENCES . . . . . . . . . . . . . . . . . 48 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . 57 APPENDICES A. EIGHT POINT SELF-COMPLEMENTARY GRAPHS . . . . . 58 B. COUNTS OF SELF—COMPLEMENTARY GRAPHS . . . . . . 62 iv 3.3 3.4 LIST OF FIGURES AND TABLES Two isomorphic graphs. . . . . . . . . . . Complementary graphs. . . . . . . . . . P the self-complementary graph having 3’ - four pOInts. . . . . . . . . . . . . . The two self-complementary graphs having five pOintSO O O 0 o o o o o o o o o o o o o o o a) A graph, b) a subgraph, c) an induced subgraph . O O I O O O O O O O O O O O O O O A three point graph. . . . . . . . . . . . Self-complementary graphs and complementing permutations O O O O I O O O O O O O O C An adjacency scheme for a self-complementary graph 0 O O O O O O O O I 0 O O O O O O I O The self-complementary graph constructed from the scheme in Figure 3.2. . . . . . . . . . Subgraphs induced by cycles of a complementing permutation O O O O O O O O I O O O O O O The two possible P3 subgraphs if d(l,2) = —l.. The two possible P3 subgraphs if a(l,2) = 1. . An adjacency scheme. . . . . . . . . . . The two P3 subgraphs furnished by the first cycle. . . . . . . . . . . . . . . . . . The two P3 subgraphs furnished by the second cycle. . . . . . . . . . . . . . . . . . . An adjacency scheme. . . . . . . . . . . . . . The graph constructed from the scheme. . . . V Page l6 17 18 26 26 29 3O 3O 36 36 LIST OF FIGURES AND TABLES (cont'd.) FIGURE Page 5.3 An adjacency scheme. . . . . . . . . . . . . . 46 5.4 The graph constructed from the scheme. . . . . 46 A.1 Eight point self-complementary graphs. . . . . 58 TABL E B.l Exact and asymptotic counts of self-complementary graphs. - O O O O O O O O O O O O 0 O O I O 0 vi INTRODUCTION Heretofore, self—complementary graphs have been the subject of little investigation. For a given positive integer n, algorithms for constructing all self-complemen- tary graphs having n points have been developed, and a formula for the number of such graphs has been derived. Other results have been obtained, chiefly concerning special types of self—complementary graphs: regular, quasi-regular and cyclic. Also, the characteristic polynomials of the standard 0,1 adjacency matrices of special self-complementary graphs have been studied. Hewever, structural properties of self—complementary graphs have not often been considered. In this thesis, we present a new algorithm for con- structing all self-complementary graphs and use it to obtain several results concerning the structural character— istics of these graphs. In addition, a different adjacency matrix is defined and we show that the eigenvalues of the matrices corresponding to special self-complementary graphs are relatively easy to find. Some properties of the eigenvalues of these matrices are presented. Finally, results are given concerning the degrees of the points of self-complementary graphs. CHAPTER I SURVEY OF THE LITERATURE Only two articles on self-complementary graphs them— selves and two on their enumeration have been listed in the Mathematical Reviews. In 1963, Read [4] presented formulas which enumerate, for a given n, the number of non-isomorphic self-complementary graphs having n points. In 1962 and 1963 articles were published by Sachs [6] and Ringel [5], respectively, in which each presented an algorithm for constructing all self-complementary graphs having a given number of points. In addition, Ringel proved that if G is self—complementary, then the diameter of G is 2 or 3. Sachs' paper, which is more comprehensive than Ringel's, contains several results concerning special self-complementary graphs, including the matrix properties referred to in the introduction. The results of Ringel and Sachs will be acknowledged as they appear below. In 1969 Palmer [3], using Read's results, discovered a simple asymptotic formula for the number of self— complementary graphs having a given number of points. Hi5 results are referred to in Appendix B. CHAPTER 2 DEFINITIONS AND NOTATION A grgph G = G(V,E) consists of a finite set V together with a subset, E, of V(2), the set of unordered pairs of distinct elements of V. V is called the set of vertices or pgints of G, E is called the set of egggg or liggg. A graph G is connected if, for any two points vi and vj, there exists in E a sequence of edges where v. = v. and v. = v. for some k. If (v ,v )6 B then 11 1 1k 2 l v and v are the edge (vl,v2) 18 said to lgig V1 and V2, 1 2 adjacent in G, and v1 and v are endpoints of (v1,v2). The 2 number of points to which a point v is adjacent is the degree of v, written deg(v). If G has points l,2,...,n, the sequence deg(l), deg(Z),..., deg(n) is called the degree sequence of G. If G has degree sequence k,k,...,k G is regular 9; degree k. Two graphs Gl(Vl,El) and GZ(VZ,E2) are isomorphic, written G1 3’G2, if there is a one-to-one map 0 from V1 3 onto V2 such that (v,W) E E1 if and only if (OM, OM) 6E2. o is called an isomorphism of G1 onto G2 and we will write O(Gl) = G2. If G1 g'Gz and both have n points we may think of V1 and V2 as being the set {l,2,...,n} . Then a is Simply a permutation of the symbols l,2,...,n. For example, if G1 and G2 are as in Figure 2.1 N w I" N 7A 5 4 5 LI OJ Figure 2.1 Two isomorphic graphs. then the permutation c = (14) (235) is an isomorphism of G1 onto G (We will assume throughout 2. that all permutations are represented as the product of disjoint cycles.) If G1 = 62 = G then the permutation G such that 0(6) = G is called an automorphism of G. An automorphism of a graph G, then, is a relabeling of its points which preserves adjacency. For example, the permutation O = (12)(35) is an automorphism of the graph G2 above. The set of all automorphisms of a graph G, together with the operation of permutation multiplication, is a group, [—16), called the agtomorphism group of G. The complement, E, of a graph G is the graph with the same point set as G such that two points are adjacent in G if and only if they are not adjacent in G. For example, the graphs below are complements of one another. ’4 Figure 2.2 Complementary graphs. Q! If G G then G is self—complementary. There are no self-complementary graphs having two or three points. There is one self—complementary graph having four points, which I_J Figure 2.3 P3, the self-complementary graph we shall denote P3. having four points. There are two self-complementary graphs having five points. Figure 2.4 The two self-complementary graphs having five points. The graph having n points and all pairs of points adjacent is called the complete graph with n points and is denoted Kn' It is easy to see that Kn has (2) =.fll%:£h lines. A subgraph H(V1,El) of a graph G(V,E) is any subset Vl of V together with any subset E1 of E such that if (v,w) 6 El then V'E V1 and ‘w 6 V1. A subgraph of G induced by the sUbset V1(: V is the sabgraph with point set V1 and all lines of G having both endpoints in V1. For example, the figure below presents a graph, sub— graph and an induced sUbgraph. Li (a) (b) (C) Figure 2.5 a) A graph, b) a subgraph, C) an induced subgraph. There are several matrices which can be assigned to a graph. The standard 0,1 adjacency matrix has its i-j entry 1 .7 if i and j are adjacent, 0 otherwise. The adjacency matrix which we shall use was found by Seidel [7] to have advantages over the standard 0,1 adjacency matrix. It is particularly well suited for the study of self-complementary graphs. The adjacency matrix, A(G) = (aij)’ of a graph G having points labeled l,2,...,n has as its i-j entry 0 if i = j aij = 1 if i is not adjacent to j -1 if i is adjacent to j. If G is the graph in Figure 2.6 A 2 3 Figure 2.6 A three point graph. then 0 -l l A(G) = ~l O -1 1 -1 O 0 Since aij = aji’ the matrix A(G) is symmetric and has real eigenvalues. Other definitions and notations will be given as the need arises. For a complete lexicon of graph theory vocabulary, see Harary [2]. A general review of basic matrix theory can be found in Finkbeiner [l]. The end of a proof will be denoted by the symbol ' []'. CHAPTER 3 THE CONSTRUCTION ALGORITHM Let IL(G)| be the number of lines of graph G. If G has n points then IL(G)|+ |L(5)| = |L(Kn)l = (2) = rug-1) If G is self-complementary then IL(G)| =|L('5)l so that _ l_n _ ngn-l) IL(G)| -2(2) - 4 . Hence either n or (n-l) must be divisible by 4. This proves Theorem 3.1. If G‘g G and G has n points then n E O or 1 (mod 4). We show below, by developing an algorithm, that if n E O or 1 (mod 4) then there exist self-complementary graphs having n points. Before discussing this construction algorithm we mention a property of self—complementary graphs which follows immediately from the definition. In Theorem 3.2. If G 'G then G is connected. Proof: It is easy to Show, and well known, that G and G cannot both be disconnected. Let G QUE have n points labeled from 1 to n. From the definition, we know that there exists a permutation, O, of the symbols l,2,...,n such that G(G) ='G. we will call O a complementing_permutation or anti-automorphism of G. For example, particular complementing permutations corresponding to the four and five point self-complementary graphs are given in Figure 3.1. 5 1 3 1 3 5 Graph 2M4 2 4 - A . l 2 4 3 complementing (1234) (1234)(5) (1234)(5) permutations (1432) (2453)(1) (l432)(5) Figure 3.1 Self-complementary graphs and complementing permutations. Notice that non-isomorphic graphs may have the same complementing permutation and that a particular graph may have more than one complementing permutation. The structure of a complementing permutation is described in the follow— ing theorem due, independently, to Ringel [5] and Sachs [6]. Thegrem 3.3. Suppose that 0(6) 5'5 and that G has n points. lO 1) If n 5 O(mod 4) then each cycle of a has length divisible by 4. 2) If n 5 1(mod 4) then a has exactly one cycle of length l and all other cycles have length divisible by 4. .Prggfz If p is any complementing permutation of G then the pair of points (i,j) has the opposite adjacency relation of the pair (p(i),p(j)). Hence p can fix no pair of points. Therefore a can have no transpositions and at mOst one 2k+1 , l-cycle. Note that any odd power of G, such as d is also a complementing permutation of G. Thus 6 can have no cycles of length 2k+1 or 4k+2 because 62k+l will have at least 2k+1 l-cycles in the former case and at least 2k+1 transpositions in the latter. Therefore all cycles in d, with the possible exception of a single l-cycle, have lengths divisible by 4. D As an immediate corollary we have Corollary 3.1. If n = 4k+l then G has a least one point of degree 2k. Proof: The point fixed by any complementing permutation must be adjacent to exactly half of the remaining points.El It was observed in the proof of Theorem 3.2 that if 62k+1 '- o'(G) = G then (G) = G. It follows that {G]o(G) =5} 3 ]G]62k+1(G) =5}. 11 As the labeling of the points of G is immaterial, it is apparent that, if a and p have the same cycle structure, then {G lO‘(G) =5}: {GI p(G) =5}. Now, we can eliminate all odd prime power divisors of the cycle lengths of O by raising O to the product of such odd powers. This new permutation 6' will have all its cycle lengths powers of 2. (Of course, none can be of length 2.) Therefore, successive odd powers of O' will have the same cycle structure as 6'. Consequently, if we can find, for permutations on n symbols, (1) U {GI a' (e) = a} C" where the union is taken over all possible cycle structures where the cycles have 2-power lengths, we will have found all self-complementary graphs having n points. We remark that a particular graph may occur in several of the individ- ual sets. For example, four of the graphs in Appendix A have an 8-cycle as well as a two 4-cycle complementing permutation. The following algorithm, suggested by the algorithm of Ringel [5], provides a method for constructing (but not uniquely) all self-complementary graphs having a given complementing permutation a with cycles having 2-power lengths. This algorithm is basic to the entire thesis and will be referred to often. 12 Construction Alggrithm. Assume, without loss of generality, that the symbols in a are numbered consecutively from 1 to n, and that the cycles are of non-decreasing lengths 4k 4k (except for a possible l-cycle (n) at the 1, 2, on. end). Here, of course, k1, k2, ... are powers of 2. We focus our attention on the following symbols: the symbols 2, 3, ..., 2k1 + 1 of the first cycle, the first 4kl symbols of each other cycle, and the symbol n if (n) is a l—cycle. This set will be called the Egggg of the symbol 1. (We will construct a graph G with points labeled 1,...,n and therefore we identify the symbols in a with the points of G.) Consider the (unordered) pairs (l,j) where j is in the range of 1. For each pair we arbitrarily decide whether or not 1 and j will be adjacent in G. Once this choice has been made, the same choice must apply to the pairs 2' 2i. . (O 1(1), a (3)) 1 = 1, 2, ..., 2ki where j is in a cycle of length 4ki . If j = n = 4k + 1 3 let i = l, 2, ..., 2k1. The opposite adjacency relation must apply to the pairs (a21‘1<1>, 021‘1(j)) where i is as above. 13 This completes the first stage of the algorithm. We next reduce the problem by replacing the permutation O by the simpler permutation 0*, on n—4k1 symbols, obtained from O by deleting its first cycle. Now, apply the procedure out- lined above to 0*. Then delete its first cycle and continue until no cycles remain. The procudure will terminate since a has a finite number of symbols. This completes the algorithm. We must now show that, in fact, a well-defined graph is determined and that it is self—complementary. Theorem 3.4. As a result of performing the Construction Algorithm: 1) the adjacency relation between points is well- defined, 2) every pair of points is assigned an adjacency relation, 3) the graph thus constructed is self-complementary. Proof: 1) The pair (l,j) cannot be sent to itself by an odd power of 0 because clearly 021-1 621-1 (3) F j, and if (1) = j then j is the symbol 2i in the first cycle and 021-1(j) 5 41-1 (mod 4k1) E -l(mod 4) # 1. Thus the pair (l,j) can never be assigned simultaneous adjacency and non-adjacency. The same argument applies to the pairs (61(1), Gi(j)) and carries over for all stages of the Construction Algorithm. 2) It is clear that, once the first point of each l4 cycle has its adjacencies determined with all the points which follow it, all adjacencies of the graph are determined. For the remainder of this thesis we adopt the notation 0 if i = j (2) d(i,j) = 1 if i is not adjacent to j -1 if i is adjacent to j. Thus a(i,j) = aij is the i—j entry of the adjacency matrix A(G). By the Construction Algorithm, k . k . k . . (3) 0(6 (1), a (3)) = (-1) a(l,J). If jIg 4kl’ that is if j is in the first cycle, then letting i = 1 and j = 4k + l - j in (3) we see that l a(1,j) = (—1)j"l a(1,4k + 2 - j) 1 Hence, all adjacencies in the first cycle are determined if we know the adjacencies between 1 and 2’ 3, coo, 2k1+l The adjacencies between 1 and the first 4k1 points in any other cycle determine all adjacencies between the first cycle and that cycle. This is because the adjacencies between 1 and the first 4kl points form a pattern of period 4kl since kl divides kj for j > 1. We have shown, then, that the adjacencies among points in the first cycle and the adjacencies between the points of the first Cycle and all other points of the graph are determined once the adjacencies between 1 and the points in its range are given. Repeating the argument for each 15 stage of the Construction Algorithm proves that all adjacen- cies of the graph are determined. 3) Now that we have shown that the adjacencies are unique and that all possible adjacencies are determined, it follows immediately that the graph constructed from the Construction Algorithm is self-complementary, because the given permutation a is an isomorphism. That is, G(G) = G; We have observed that every self—complementary graph having n points possesses a complementing permutation O with cycles having 2—power lengths. Hence, for a given such permutation, as the various arbitrary choices of initial adjacencies are chosen, the Construction Algorithm will produce,possibly with repetitiOn, all self-complementary graphs having 0 as a complementing permutation. That is, it is possible to find {GI 0"(G) =5} so that, according to (1), all self-complementary graphs having n points can be determined. We illustrate the application of the Construction Algorithm on a permutation O having 9 symbols, to construct a self-complementary graph having 9 points. Let G = (1234)(5678)(9). The range of l is 2,3,5,6,7,8,9. 16 For 5, the range is 6,7,9. Let G(i,j) be as in (2) and let us choose the values . _ -l for j = 2,5,8 “(13) ' {l for j = 3,6,7,9 . —l for ' = 6 9 G(S’j) = l for j = 7’ ’ We shall represent this adjacency assignment schematically as in Figure 3.2. (1 2 3|4) (5 6 718) (9) Figure 3.2 An adjacency scheme for a self— complementary graph. In the scheme, if a line is not drawn from an initial point to a point in its range, non-adjacency is implied. From the Construction Algorithm we infer that G(l,4) = 1 = ‘(I :2: :ggggw “‘3’j’ = if: :3: 3 Z fjij;,8,9 “”J’ {i§:§:fi%§“9 I l—‘ d(5,8) l7 . _ —l for j = 5,8 0‘ (6’3) ' {I for j = 7,9 . _ —l for j = 8,9 a(7,3) 1 for j = 5,6 a(8 .) _ —l for j = 6,7 ’3 " 1 for j = 5,9 The graph G, determined by the Construction Algorithm, is given in Figure 3.3. Figure 3.3 The self—complementary graph constructed from the scheme in Figure 3.2. There are several important corollaries which follow immediately from Theorem 3.3, the Construction Algorithm, and Theorem 3.4. Assume throughout that G has n points and that O'(G) = 5. Corollary 3.2. The set of points in any subset of the cycles of a will induce a self-complementary subgraph of G. Proof: O, restricted to the symbols in the chosen cycles, will, by the Construction Algorithm, produce a self-comple- mentar ra h. Y 9 P E] 18 In the example above, the sets {1,2,3,4,9j and {5,6,7,8} induce the subgraphs shown in Figure 3.4. f /\ LI Figure 3.4 Subgraphs induced by cycles of a complementing permutation. H M 4:. wt Corollary 3.3. In any cycle of O with length greater than 1, the points alternate in degree, the sum of the consecutive degrees being n-l. in a Proof: If i 2 l is adjacent (on the left, say) to i cycle of G then G(il) = i2. Hence deg(ll) In G = deg(12) in G = n-l-(deg(12) 1n G).L__1 In the example above, the first cycle has degrees 3,5 and the second has degrees 4,4. Corollary 3.4. Let G have point set V. If S (IV contains all points of certain degrees, and T is the set of points of degrees complementary to those in S, then S L/T'induces a self-complementary subgraph of G. nggf: By Corollary 3.3 the set of points in S LIT is fixed under O and must therefore constitute a subset of the cycles of 6. Hence, by Corollary 3.2, the induced subgraph 19 is self-complementary. Note that if S(\ T = D then S and T have the same number 2 of points, say m, and there are %; lines between the sets (half the possible number). Corollary 3.5. If H is any subgraph of G induced by the point set S Civ and we interpret G(H) to be the graph induced by the point set {6(1), i 6 S} , then n2 0’ (H) H. In particular if H is a self-complementary induced subgraph of G then 01(H) Q’H i=l,2,... Proof: i1 and i2 in S are adjacent in H if and only if 0(il) and 0(i2) are non-adjacent in 0(H). Corollary 3.6: The set of automorphisms and anti—automorphisms of G form a group in which rYG) is a (normal) subgroup of index 2. It follows that G has as many automorphisms as anti-automorphisms. Proof: We know that rkG) is a group. Since 62(6) = G it follows that d_l(G) = G (and that 6(5) = G). Also, if p(G) = a then 0") and pd belong to r(G) .E] 20 Corollary 3.7. 17G) is a non-trivial group. Proof: Since 0' has order divisible by 4, 0'2 cannot be the identity permutation. But 0'2 6 RG) OD The properties of a self-complementary graph having n = 4k+l points can be determined directly from a self- complementary (induced) subgraph of 4k points. In fact, if 6(G) = G and G has n = 4k+l points then from Corallary 3.1, the point n has degree 2k. Moreover, by the Construction Algorithm, n is joined to alternate points in each cycle of 6. By Corollary 3.2, if we remove the point n and its 2k lines we will obtain a self-complementary graph having 4k points. Conversely, if we start with a self-complementary graph G having 4k points and complementing permutation p, we can easily construct all self-complementary graphs having 4k+l points and having G as a 4k point induced subgraph: simply connect the new point to alternate points in each cycle of p. By the Construction Algorithm, this new graph will be self-complementary. Observe in Figure 3.1 that the two five point graphs are obtained from the four point graph with complementing permutation (1234) by joining 5 to l and 3, and to 2 and 4, respectively. Hence we shall restrict our attention in the remainder of the thesis to self-complementary graphs having 4k points. CHAPTER 4 THE DECOMPOSITION THEOREM In this chapter we show that every self-complementary graph having 4k points possesses a collection of k disjoint induced subgraphs isomorphic to P 3. First, we investigate some properties of self- complementary graphs which possess a complementing per- mutation consisting of a single cycle. Graphs of this type have been considered by Sachs [6]. The present results go beyond those of Sachs, however Sachs observed part 2) of the next theorem. Theorem 4.1. Let G(G) = G where then a: (12 4k) 1) each odd-labeled point of G is adjacent to exactly k even-labeled points and each even-labeled point is adjacent to exactly k odd-labeled points 2) G has points of two degrees: for some r such that k S_r S 3k-l there are 2k points of degree r and 2k points of 21 22 degree 4k—l-r. Moreover, for every such r, at least one self-complementary graph G with 6(G) = G exists having 2k points of degree r and 2k points of degree 4k-l-r. 2329:: 1) Using the o(i,j) notation of (2) in Chapter 3 we obtain - a(4k+2-2i,l) - a(l,4k+2-2i). Hence 1 is adjacent to 2i if and only if it is Egg adjacent to 4k+2-2i. Therefore, 1 is adjacent to exactly half of the 2k even-labeled points. By the Construction Algorithm, this implies that every odd-labeled point is adjacent to exactly k even-labeled points. Similarly we have 4k+l-Zi C4k+l—21 O4k+1—21 d(2,21+1) (—l) a( (2), (21+l)) = - (1(4k-l'4" (21431) :2) - a(2,4k+4—(Zi+l)) en: that 2, and hence any even-labeled point, is adjacent tx) exactly k of the odd-labeled points. 2) As a is a single cycle, by Corollary 3.3, there arse only two degrees of points in any graph G such that 0’03) ='G. These degrees alternate among the symbols in 0 SC) that the odd-labeled points have the same degree, say r, arni the even—labeled points have the complementary degree 23 4k-l-r. By 1) we have k S'r and k < 4k-l-r. that is, k‘S r‘S 3k-l. Let r be given such that we indicate hOW'tO construct a graph G such that G(G) =‘G and the odd-labeled points have degree r. Since 1 is adjacent to k even-labeled points, we must join 1 to exactly r-k oddblabeled points. Since 4k—2i _2. _ . . 4k 1 04k 21(1), 0 (21+1)) d(l,2i+l) = (-l) a( a(4k+l-2i,l) a(l,4k+2—(21+l)) it follows that, if 1 is joined to s of the odd-labeled points 3,5,000’2k-l it is also joined to s of the points 2m3,2ms,n.,4ha. The adjacency relation between 1 and 2k+1 = 4k+2 - (2k+1) implies no other adjacency. If r-k is even, join 1 to £35 24 of the points 3,5,...,2k-l, to any subset of the points 2,4,...,2k and apply the Construction Algorithm. The graph constructed will have the odd-labeled points of degree r, the even— labeled points of degree 4k-l-r. If r-k is odd, join 1 to the point 2k+1, to Ezgli- of the points 3,5,...,2k-l and to any subset of the points 2,4,...,2k and apply the Construction Algorithm. The graph constructed will, as above, have the odd-labeled points of degree r, the even—labeled points of degree 4k-l-r.E) d— Remark: Sachs calls a graph G quasi—regular if G G has 4k points, 2k of degree 2k-l and 2k of degree 2k. By the Construction Algorithm, quasi-regular graphs can be constructed for all k. If we construct a new graph G' from G by adding a new point, of degree 2k, joined to the points of G of degree 2k-l, then G' will have 4k+l points and will be regular of degree 2k. Conversely, given a regular self— complementary graph, it must have 4k+l points, for some k, and be regular of degree 2k. If, for a given complementing permutation, we remove the fixed point and its 2k lines, 25 a quasi-regular self-complementary graph having 4k points will remain. We now present the fundamental lemma which will lead to the Decomposition Theorem, one of the main results of the thesis. Lemma 4.1. Let G(G) ='G, o = (l 2 ... 4k). G contains a subgraph isomorphic to P induced by the set of points 3 {,l,2,2i—l,2i}- for some i such that (l) 2 < i < k+l. Proof: Let i be the first positive integer for which a(l,21) = — a(l,2). Then the subgraph induced by the set {l,2,21-l,2i} is isomorphic to P Because, if 3. a(1,2) = -l = d(2i-l,2i) then a(l,2i-2) = -l and a(2,2i-1) = 1, Also d(l,2i-l) - a(2,2i) 26 so the subgraph induced by the set {l,2,21-l,21} will be one of those in Figure 4.1. l[—‘—“‘2i—l 1] lZi-l 2 21 2 21 subgraphs if a(l,2) = —l. Figure 4.1 The two possible P3 If, on the other hand, d(l,2) = l = d(21-1,2i) then the subgraph induced by the set {1,2,21-1,2i} will be one of those in Figure 4.2. lx2i—l l: :Zi-l 2 2i 2 2i Figure 4.2 The two possible P subgraphs if d(l,2) = 1. 3 To show that such an i, as in (1), exists, observe that if a(1,21) = a(l,2) i = 2,3,...,k then, from the proof of 1), Theorem 4.1, a(l,2k+2) = d(1,4k+2 - (2k)) = - a(1,2) 27 so that the subgraph induced by the set [1,2,2k+1, 2k+2} must be isomorphic to P . 3CD We are now in a position to present the main result of this Chapter. Theorem 4.2. (The Decomposition Theorem). If G "=I G has 4k points then G possesses a collection of k disjoint induced subgraphs each isomorphic to P3. 2599;: Let G be a complementing permutation of G whose cycle lengths are powers of 2. (We kn w from Chapter 3 that at least one such permutation exists.) By Corollary 3.2 the points in each cycle of O induce a self-complementary sub- graph of G. It thus suffices to Show that these subgraphs have the desired decomposition. Consider a cycle of G of length 2m. For convenience of notation, let the cycle be (1 2 3 2‘“). Suppose, according to Lemma 4.1, that 2i is the first even- labeled point such that [1,2,2i+1,2i+2} induces a P3 subgraph of G. Consider the set of odd integers (2) {02ti(l)] = (a£§ t = O,l,2,... . 28 If i = 2 -s , 5 odd then, since t = 2m-l—r is the smallest integer such that 2ti a O (mod 2m), the set (2) will contain Zm-l-r distinct odd integers. Thus m—2—r 2 distinct pairs of odd integers 4i (1, 021(1)), (0 (1), a6i(1)), ... are determined. If r > 0, select an odd integer j < 2m which is not In [afik and obtain a new set {Sam} t = O,l,2,... . 2m-2-r new disjoint pairs This set will determine, as before, of odd integers. We continue until every odd integer less than 2m belongs to some set. 2r such sets will be con— . . -2 . . . . structed, thus determining 2m dISJoInt pairs of odd integers. For each pair - 21 . (23+1, O (23+1)) thus determined, we associate the following pair of even integers (2j+2, 021(2j+2)) 29 and observe that the subgraph induced by the set . . 2i . 2i . 23+l, 23+2, O (23+l), O (23+2) is isomorphic to P . This is because the above point set 3 is the image of the set {1, 2, 21+1, 21+2} under 623, so that Corollary 3.5 applies. Hence a cycle of O with length 2m furnishes a set of 2m-2 disjoint induced subgraphs isomorphic to P . Therefore, assembling such a set 3 for each cycle, we obtain a collection of k disjoint induced subgraphs of G, each isomorphic to P3.D For example, let G be determined by the adjacency scheme in Figure 4.3. (1 2 3 4 5|6 7 8)(9 1O 11 12 13|14 15 16) Figure 4.3 An adjacency scheme. Since, from Theorem 4.2, i = l for the first cycle and i=2 for the second, the set, as in (2), for the first cycle is {1, 3, 5, 7} 'and for the second cycle the sets are {9, l3} and {11, 15} . Thus the first cycle produces the subgraphs in Figure 4.4 and the second produces those in Figure 4.5. 30 Figure 4.4 The two P3 subgraphs furnished by the first cycle. 9 13 ll 15 10: :14 12: :16 Figure 4.5 The two P3 second cycle. subgraphs furnished by the CHAPTER 5 ADJACENCY MATRICES In this chapter it is shown that adjacency matrices corresponding to certain self-complementary graphs have a special form which simplifies the calculation of their eigenvalues. We first derive some additional properties of the adjacency matrix defined in Chapter 2. Theorem 5.1. If G has 2k points and A is an eigenvalue of 2 A(G) then Ajfl- is an algebraic integer. In particular, we conclude that l) A(G) is non-singular 2) If A is an integer then >\is odd 3) If )(2 is an integer then A2 is odd 4) If a graph H has 2k+1 points then the rank of A(H) is at least 2k. Proof: Consider the matrix A2(G). Each diagonal entry is 2k-l. The off—diagonal entries, being the inner—products of two rows of A(G), consist of the sum of 2k—2 (+l)'s and (-l)'s and hence are even integers. Therefore the matrix 31 32 has integer entries and thus has algebraic integer eigen— values. That is, if A is an eigenvalue of A(G) then AZ-l 2 is an algebraic integer. Since - %-is not an algebraic integer, Azyb. Therefore A(G) is non-singular. Statements 2) and 3) follow immediately. If H has 2k+1 points then deletion of any row and its corresponding column from A(H) leaves an adjacency matrix for a graph having 2k points which is, by l), non—singular. Statement 4) then follows. Let G with points l,2,...,n have adjacency matrix Al A(G). If G = GI and the points of G are labeled l,2,...,n 1 then we know that there is a permutation O of the symbols l,2,...,n such that O G = G . ( ) 1 Corresponding to a, there is an nxn permutation matrix P = (pij) defined by 1 if G(i) = j pij = 0 otherwise. The equation G(G) = G1 33 becomes, in matrix form, PT A(G) P = A(Gl). Conversely, if Q = (qij) is any nxn permutation matrix, then QT A(G) Q will be the adjacency matrix of a graph, G1, isomorphic to G. In fact, if p is a permutation on l,2,...,n with p(i) = j if and only if qij = 1 then II C) pm This proves Theorem 5.2. If and G1 are graphs having n points G ’e‘.’ l,2,...,n then G G1 if and only if there exists an nxn permutation matrix P such that PT AM)P=M%L A property of the eigenvalues of an adjacency matrix is given in the next theorem. Theorem 5.3. If the graph G having n points has adjacency matrix A(G) with eigenvalues algooo,an then a2=MmD. 1=l 34 Proof: The diagonal entries of A2(G) are all n—l. Therefore trace (A2(G)) = n(n-l). . . 2 . . If ai is an eigenvalue of A(G) then ai IS an eigenvalue of A2(G). Since the trace of a matrix is the sum of its eigenvalues, the result follows. Having observed these preliminary properties, which hold for any graphs, we now consider matrices and eigen— values of self-complementary graphs. Since, for any graph G, A(G) = ”A (G) 9 if G‘1 G, there exists a permutation matrix P such that -l T P A(G)P = P A(G)P = —A(G). Since A(G) is similar to -A(G), both have the same eigen— values. But ai is an eigenvalue of A(G) if and only if -ai is an eigenvalue of —A(G). We conclude that the eigenvalues of A(G) occur in opposable pairs (except for the eigenvalue a = 0 if n is odd). If G has 4k points we can list the n eigenvalues as +a i_a1, __ 2, ... , i_a2k. If G has 4k+l points, 0 must be an eigenvalue of multiplicity one by 4) of Theorem 5.1, and we can list the eigenvalues as tal, 12:12,, :a2k, 0. 35 From Theorem 5.3 we see that, for a self-complementary graph G having n points and adjacency matrix A(G) with non-zero eigen— values ial, ,-I_-a2k , k=[§] we have 2k Zai2= (3). i=1 We summarize these results as 'd Theorem 5.4. Let G ‘5 have n points and adjacency matrix A(G). Then 1) The non-zero eigenvalues of A(G) occur in opposable pairs. If :al, 000 ,iaZk ) k=[ ] 6):: are the non-zero eigenvalues of A(G) then 2k : 2 n all " (2) 0 i=1 2) If G has 4k+l points then A(G) is singular with rank 4k. We now consider self-complementary graphs with the property that they possess a complementing permutation having cycles of equal length. If G QNG has 4k points and 36 possesses a complementing permutation 0 whose cycles have equal length, then A(G) can be transformed into the direct sum of two matrices of dimension 2k, thus Simplifying the determination of its eigenvalues. We emphasize that any relabeling of the points of any graph G will give rise to an isombrphic graph G1 with adjacency matrix similar to A(G). The same effect is obtained by relabeling rows and columns of the adjacency matrix rather than relabeling the points. If G has a complementing permutation consisting of the product of cycles of equal length, we will use this latter option to construct a matrix similar to A(G) whose eigenvalues are more readily determined. Before proving it, we illustrate this process with an example. Let U = (l 2 3 4 5 6 7 8) and let G be determined by the adjacency scheme in Figure 5.1. (l 2 3 4 5'6 7 8) VJ Figure 5.1 An adjacency scheme. Then G is the graph in Figure 5.2. 3 Figure 5.2 The graph constructed from the scheme. 37 It follows that r0 — + — + + + +. —O+-+--- ++O-+-++ A(G) = _ - _ O + - + — (where — means -1 + + + + O - + — and + means 1). + - - - - O + - +—++++0— L+-+-----O] Note that 62 = (l 3 5 7)(2 4 6 8) is the automorphism rotating G through 90°. If we list the rows and columns of A(G) in the order + +o+ o+ ll +++ + + I I I O I +o++ +++ I + o+ I r: I I l + I I O This new Al can be described as a symmetric 4 x 4 matrix whose entries are 2 x 2 matrices of special form. On the diagonal we have iI‘féI and elsewhere we have that-[1’3- 38 Let s = O l l O and _ 2 _ l 0 e - S - O l 3 then ' 7 S -eI-S e+s -eI-s A1 = -e+s -s e-s -e—s e+s e—s s -e+s -e+s —e-s -e+s -s . . ' 2 2 If we replace 5 by Its eigenvalue 1 and e = s by l = l we obtain the 4 x 4 matrix [1 O 2 0] B1 = -l O -2 2 O l O L0 -2 O -1‘ If we replace 5 by its other eigenvalue -1 and e = 52 by (-l)2 = l we obtain the matrix ”-1 -2 O —21 B = -2 l 2 O O 2 -l -2 ]:2 O -2 l . Now, Bl has eigenvalues i_l, i_3, B2 has eigenvalues :_3, i_3, and the eigenvalues of A(G) are i_l, i_3, i_3, + 3, precisely those of B1 and B . In fact, if we transform A 2 l by the product RP where 39 '1 -1 O O O O O O-1 1 1 O O O O O O R = 3:: O O 1 -1 O O O O ‘/2 O O 1 1 O O O O O O O O 1 -1 O O O O O O 1 1 O O O O O O O 1 -1 [O O O O O O 1 1 and I1 0 O O O O O 0‘1 O O O O 1 O O O P = O 1 O O O O O O O O O O O 1 O O O O 1 O O O O O O O O O O O 1 O O O O 1 O O O 0 LO 0 O O O O O 1_ we obtain (RP)-l A1(RP) = B1 0 0 B2 where O is the 4 x 4 zero matrix. This example illustrates the result of the main theorem of this Chapter. Theorem 5.5. If a self-complementary graph G, having 4k points, possesses a complementing permutation consisting of the product of cycles of equal length then: 4O 1) A(G) is similar to a symmetric 2k x 2k matrix whose entries are polynomials in the matrix s = [(1) (15] . The diagonal entries are S or -S and all the other entries are :,e i_s. 2) If we form B by letting e = s = l and B by l 2 letting e = -s = 1 then the eigenvalues of A(G) are those of B1 and 32' Proof: 1) Let G(G) = G where G = ( l 2 ... 4kl)(4kl+l ... 8kl)...(...4k). Form Al from A(G) by labeling its rows and columns in the order '1, 2k +1, 2, 2k +2,..., 2k 4k 1 l 1’ 1 4k +1, 6k 1 +1, 4k +2, 6k +2,..., 6k 8k 1 l l’ l 1 For the entry at row i and column j put a(i,j). We focus our attention on the consecutive pairs (1, 2k1+1),(2, 2kl+2),..., (4k—2k 4k). 1: Consider the 2x2 smeatrix formed by 2 of these pairs. . . . (m,2kl+m) . . . I? ‘3] .7 I'D QFr+ + r,- 41 There are two cases. Case 1) If t = m then we have a block on the diagonal of A and so 1 a = d = 0. Now, b = G(t, 2kl+n0 and 2k1 2kl c = G(2k1+t,m) = (1(0 (t), 0' (2kl+m)) 2k1 = (-l) G(t, 2kl+m) = OL(t, 2kl+m) = b. Therefore a b [c a] = i s - Case 2) If t # m then a = d(t,m) and b d(t, 2kl+m). Thus, since all cycles have the same length 4k1, we have 2k a(2kl+t, 2kI+m) = 0(6 2k 1(t), a 1(m)) D.) II 2k (1-1) 1 d(t,m) = a a(t,m) and 42 2k 2k 1 (t), o 1(2kl+m) 0 II OL(2kl + t,m) = a(o 2kl (-l) d(t, 2kI+m) = a(t, 2k1+m) = b. Therefore a b _ [c4 This completes the proof of l). 2) The matrices e and s are simultaneously diagonal— ized by the matrix 2 O [O O] , r-l(-e-s)r [O O] -1 o 2 , r (-e+S)r II ' II Oto I0C)I (l) r—l(e+s)r r-l(e-s)r H ICC) I |_._O_J Let Pr '1 r R: ' O Q r L _ 43 will be composed of 2x2 blocks of the forms listed in (1). Those on the diagonal of A are of the first two types 2 whereas the off-diagonal blocks are of one or more of the other four types. It can be seen that the i-j entry of A2 is zero whenever i+j E 1 (mod 2). Therefore, if we transform A by the 4k x 4k permutation matrix P whose columns are 2 respectively, columns 1, 3, 5, ..., 4k—l, 2, 4, 6, ... , 4k of the unit matrix of dimension 4k, we will obtain -1 P A2 P — C O O D The entries of C are the "upper-left" entries of the 2x2 blocks in A2 and the entries of D are the "lower-right" entries of those 2x2 blocks. Now, observe that, in the 2x2 matrices in (1), if we let e = s = l we obtain the upper- left entries and if we let e =-s = l we obtain the lower- right. Therefore C = B1 and D = B2. Finally, since A(G) is similar to Bl O O B 2 l the eigenvalues of A(G) are those of B1 along with those of B2 El Recalling that A(G) has opposable eigenvalues, we remark that it can be shown that B1 and B2 themselves have 44 opposable eigenvalues. In Theorem 5.1 we observed some properties of the eigenvalues of adjacency matrices of arbitrary graphs. For self-complementary graphs of the type considered in Theorem 5.5, more specific properties exist. Theorem 5.6. Let G be as in Theorem 5.5. If )(is an eigenvalue of A(G) then 2 _Z_:_£ 4 is an algebraic integer. In particular, if )‘2 is an integer then A2 E 1 (mod 4) grggfz The matrices B1 and B2 in Theorem 5.5 have 1 and -l on the diagonal and O, 2 or —2 off the diagonal. Hence B = I + 2M and B = I + 2M2 where M1 and M2 have integral entries. Therefore the eigenvalues of M1 and M2 are algebraic integers. Now, 2 . Bi = I + 4Mi + 4Mi , i — 1,2 and so 45 If ,X is an eigenvalue of A(G) then, by Theorem 5.5, .X is and eigenvalue of B1 or B2 so that where x is an eigenvalue of M or M . In any case, x is an 1 2 algebraic integer and so is x2 + x. Clearly if ,X 2 is an integer, then [*2 5 1 (mod 4) since the only rational algebraic integers are integers. It is suspected that the result of Theorem 5.6 holds for any self-complementary graph having n E 0 (mod 4) points. The method of Theorem 5.5 and the result of Theorem 5.6 are applicable to all ten of the self-complementary graphs having eight points, as each possesses a complementing per- mutation consisting of two 4-cycles. In Appendix A we list the ten graphs and some of their complementing permutations, together with the eigenvalues of their adjacency matrices. In concluding this chapter we observe that not all self-complementary graphs satisfy the conditions of Theorem 5.5. The following example presents a self-complementary graph having twelve points which possesses no complementing permutation consisting of three 4-cycles. Let g = (l 2 3 4)(5 6 7 8 9 10 ll 12) and consider the adjacency scheme in Figure 5.3. 46 (1 2 3I4)(5 6 7 8 9'10 11 12) Figure 5.3 An adjacency scheme. The graph G constructed from this scheme is given in Figure 5.4, where points 2 and 4 are also connected to all of the points 5, 7, 9, 11 but the lines have not been drawn. 8 1* 1m- .3 v/ / it Figure 5.4 The graph constructed from the scheme. If G has a complementing permutation 6' consisting of three 4-cycles then o"=aa where a is an automorphism of G. HOwever, the only auto— 47 morphisms of G are I, (5 9)(7 11)(6 lO)(8 12), (1 3)(2 4)(5 11 9 7)(6 12 10 8), (l 3) (2 4) (5 7 9 ll) (6 8 10 12) and, if we multiply a by any of these, the product will consist of a 4—cycle and an 8-cycle. Therefore G has no complementing permutation consisting of three 4-cycles. CHAPTER 6 TYPE—SEQUENCES Let G be a graph having n points and let p be a point of degree d. In G, p will have degree n—d-l. For this reason it is seen that for each point of degree d in a self- complementary graph having 4k points there must correspond a point of complementary degree 4k—d-l. Moreover, if G 9’ G- has 4k points and G(G) ='G then, by Theorem 3.3 and Corollary 3.3, we see that there are an even number of points in G of any given degree. These two observations lead to a simple way of denoting the degree sequence of a self- complementary graph having 4k points. Since points of complementary degree exist in equal number, we need only specify the degrees less than 2k. Since each degree has even multiplicity, the degree sequence is described by a type- seguence of k integers less than 2k, each representing 2 points of that degree and 2 of the complementary degree. For example, a self-complementary graph having 8 points and degree sequence 1, 1, 3, 3, 4, 4, 6, 6 has type—sequence 1,3 48 49 one with degree sequence 3, 3, 3, 3, 4, 4, 4, 4 has type-sequence 3, 3 etc. The type-sequences for all self-complementary graphs having eight points are given in Appendix A. Will any set of k positive integers less than 2k be the type-sequence for some self—complementary graph? Not necessarily. Certain conditions must be satisfied by the set of integers. Theorem 6.1. In the type-sequence of a self-complementary graph having 4k points, the integer i can occur at most i times. 21293: We must show that if G "=’ G has 4k points, then G, has at most 21 points of degree 1. (Of course, i < 2k.) Assume there are t points of degree i. By Corollary 3.4 and the note following it, there must be exactly t2/2 lines connecting the t points of degree i to the t points of degree 4k-i—l. Since this number t2/2 cannot exceed the number t-i of point-line incidences determined by the t points of degree i, we have 2 . t . 2 'S t-i or 50 From Theorem 4.1, if G §:G having 4k points possesses a single cycle complementing permutation then the points of G have exactly two degrees, r and 4k—l—r (assume r < 2k), with k < r. The preceeding theorem provides a more general result, applicable regardless of the cycle structure of a comple- menting permutation. CLI— Corollary 6.1. If G G has 4k points with 2k points of degree r < 2k, then r > k. Proof: The type—sequence of G has k numbers, all equal to r. By the theorem, r can occur at most r times. Therefore we must have r > k. C] There is an interesting inequality which must be satisfied by the sum of the numbers in a type-sequence. Theorem 6.2. Let dl’ d2’ "’ ’ dk be the type-sequence of G Q'G having 4k points. Then k k2: d.<2k2-k. 1: Proof: Since di < 2k - l for all i, we have 51 k 5di£k(2k-l) =2k2-k. i=1 Consider the subgraph G induced by the 2k points of degree 1 less than 2k. The sum of the degrees of these 2k points is k i=1 Since 2k2 lines join these points to the points of degree greater than 2k - l we have i=1 i 2 OS L(Gl) — 2 —=2 di—k. ' i=1 Therefore k k2 3r-l and if r > 2 we have 3r—l > 2r+l. That is, 2r+l < 4k-r—l if 2 £.r, Thus we have proven Theorem 6.3. Except for the case of P (r = k = 1), if 3 G a! G with 4k points has 2r points of degree r(r < 2k) then 53 l) r is the minimum degree in G and 2) the next higher degree in G is at least 2r+l. For example, if G]: G has 100 points, G has at most 36 points of degree 18 and if G has 36 points of degree 18, the next higher degree of any point in G is at least 37. 'We have seen that, if G gI'G'has 4k points, then, for a given r < 2k, G has an even number of points of degree r, the maximum number being 2r. The following question then arises. Is it possible, given a sufficient number of points, to find a G 2‘5 having exactly 2t points of degree r where O g_t S.r? The answer is affirmative, as will be shown in the following theorem. First, observe that if G has points of degree r where r is the smaller of the complementary degrees, then the graph must have at least 2r + 2 points if r is odd and at least 2r + 4 points if r is even. Also, if there are 2t points of degree r, then G must have at least 4t points. We may now state our theorem. Theorem 6.4. Let t and r be given positive integers with t S_r. Given any k.2 max (t, l+[r/2]) there exists a self—complementary graph G having 4k points with exactly 2t points of degree r. 54 2399:: The proof proceeds by induction on k. We first must prove the statement for k = max (t, l+[r/2]). There are two cases: gage 1) If k = t then C S.r S'Zt - l I: and by Theorem 4.1 we know there exists a G '5 having 4t points, 2t of degree r and 2t of degree 4t-r-l. gggg 2) If k = 1+[r/2] then let G be a permutation consisting of two cycles, one of length 4t and one of length 4 + 4[r/2] - 4t. Construct a graph from the cycle of length 4t having the two degrees x=r+2t-2-2[r/2] and 4t - x - l = 2t + 2 + 2[r/2] - r - 1. Note that if r is odd then x = 2t - l and if r is even then x = 2t - 2. Since we must have x > O, we are excluding, for the time being, the case t = 1 when r is even. For x > 0, construct a graph from the (4 + 4[r/2] - 4t)-cycle with the two degrees d1 = l + [r/2] - t and d2 = 3 + 3[r/2] — 3t - 1. Note that dl # r, since d1 = r means that r = l — 2t if r is odd, or r = 2 - 2t if r is even, both of which are impossible. Now, we construct the desired graph, from the Construction 55 Algorithm, by joining all points of degree x in the first cycle with the 2 + 2[r/2] - 2t points of degree d2 in the second cycle. The points of degree 4t - x - 1 will therefore also be joined to these same points. The graph thus con- structed will have the 4 distinct degrees r, 4 + 4[r/2] - r - 1 > r, dl # r and d2 + 4t = 3 + 3[r/2] + t — 1. There will then be at least 2t points of degree r. It only remains to show that d2 + 4t #’r, in order to prove that there are exactly 2t points of degree r. But, if d2 + 4t = r then r = -2t - l < 0 if r is odd, or r = -4 - 2t < 0 if r is even, both of which are absurd. We must finally consider the case t = 1 when r is even. Here, if r > 2, we consider a three cycle permutation consisting of two 4-cycles and one (2r - 4)— cycle. We construct two four point graphs from the two 4-cycles, and we construct a graph from the (2r — 4)-cyc1e having the two degrees r/2 - l and 3r/2 - 4. Join the points of degree 2 in the first 4-cycle to the r — 2 points of degree 3r/2 - 4 in the (2r - 4)-cycle and to none of the points in the second 4-cycle. Join the points of degree 2 in the second 4-cycle to all points of the (2r - 4)-cycle. Completing the con- struction will yield a self—complementary graph with six degrees of points, all distinct if r #’4. There will be 2 of degree r and 2 of degree r + 3 in the first 4-cycle, 2 of degree 3 and 2 of degree 2r from the second 4-cycle and there will be r - 2 of degree r/Q + l and r - 2 of degree 3r/2 + 2 from the (2r - 4)-cycle. Since r > 2, it is clear that we 56 have exactly 2 = 2t points of degree r. Lastly, if r = 2 and t = l, a self-complementary graph having 8 points with type- sequence 2,3 is a graph with exactly two points of degree 2. This anchors the induction. To complete the proof we now Show that if there is a graph on 4n points with exactly 2t points of degree r then we can construct a graph having 4n + 4 points with exactly 2t points of degree r. Note that we are assuming r < 2n. To construct the desired graph we simply add a 4-cycle to the complementing permutation of the graph on 4n points and join the points of the 4-cyc1e to all 2n points of degree > 2n of the graph having 4n points. This will produce a self-complementary graph having 4nI+ 4 points with exactly 2t points of degree r, since the points of the 4-cycle will have degrees 2n + l and 2n + 2, both > r, and those of the initial complementing permutation have their larger degrees (those 2.2n) increased by 2 while the smaller degrees (those < 2n), including the 2t of degree r, remain unchanged. Thus the induction is completed. We conclude by remarking that the necessary conditions on the type-sequence of a self-complementary graph given in Theorems 6.1 and 6.2 are far from sufficient. For example, it can be shown that pg type-sequence can contain the integers 2, 3, 4, 5 as a subset. The problem of determining necessary and sufficient conditions for a collection of numbers to be a type-sequence seems to be quite a difficult one. BI BL IOGRAPHY BIBLIOGRAPHY D. T. Finkbeiner. Introduction to Matrices and Linear Transformations. W. H. Freeman and Company, SanFrancisco (1960). F. Harary. Graph Theory. Addison-Wesley, Reading (1969). E. M. Palmer. Asymptotic Formulas for the Number of Self-Complementary Graphs and Digraphs. Mathematika, to appear. R. C. Read. On the Number of Self~Complementary Graphs and Digraphs. Jour. London Math. Soc. 38(1963), 99-104. G. Ringel. Selbstkomplementgre Graphen. Arch. Math. XIV (1963), 354-358. H. Sachs. fiber Selbstkgmplementgre Graphen. Publ. Math. Debrecen. 9(1962), 270-288. J. J. Seidel and J. M. Goethals. Orthogonal Matrices with Zero Diagonal. Canadian Jour. Math. 12(1967), 57 APPENDICES APPENDIX A EIGHT POINT SELF-COMPLEMENTARY GRAPHS In Figure A.1 we list the ten self-complementary graphs having eight points as well as the eigenvalues of their adjacency matrices, their type-sequences, and some complement— ing permutations. Only graphs I, II, III and IV possess 8-cycle complementing permutations. Note that if ,A is an eigenvalue and A2 is-an integer then )2 ‘5 1 (mod 4) as proven in Theorem 5.6. I. 7 Complementing permutations: . (l 2 3 4 5 6 7 8) 2 8 (1652)(3478) l 5 Type-sequence: 2,2 4 6 Eigenvalues: i.l, i.3: i.3: i.3 3 Figure A.1 Eight point self-complementary graphs. 58 Figure A.1 (cont'd.) II. 1 5 4 8 2 6 3 7 III. 1 5 8 2 6 4 3 7 IV. 1 5 8m 6 2 4 59 Complementing permutations: (1 2 3 4 5 6 7 8) (1234)(5678) Type-sequence: 2,2 Eigenvalues: :_1, 1'1, :_3, Complementing permutations: (12345678) (1238)(4567) Type—sequence: 3,3 Eigenvalues: i_l, i_l, 1.1, Complementing permutations: (12345678) (1458)(2763) Type-sequence: 3,3 Eigenvalues: i_l, i_3, :_3, i. i. 5 3 Figure A.1 (cont'd.) V. l 5 4 6 2 8 3 7 VI. 1 5 4 6 2 8 7 3 VII. 1 3 5—— 7 8 6 6O Complementing permutations: (1234)(5678) (1256)(3478) Type-sequence: 3,3 Eigenvalues: 1,1, i_l, 1.3, ipv’l7 Complementing permutations: (1234)(5678) (1432)(5876) Type-sequence: 3,3 Eigenvalues: -_I-_ l, i l, i\/ 13 i 4\/ 5 Complementing permutations: (1234)(5678) (1432)(5876) Type-sequence: 2,3 Eigenvalues: iJ—g, :J 5, i\/ 5, i/ 3 Figure A.1 (cont'd.) VIII. 1 3 5- / \ 6 2 4 IX. 1 3 4 2 X. l 3 5 8 2 4 61 Complementing permutations: (1234)(5678) (1432)(5876) Type-sequence: 2,3 Eigenvalues: i./—5_, i\/—5_ 1': (Mfg), I. (2 Hf?) Complementing permutations: (1234)(5678) (1432)(5876) Type-sequence: 2,3 Eigenvalues: i\/—5_, -I_-_\/—§ iv(2+./5), i (2 -./ 5) Complementing permutations: (1234)(5678) (1234)(5876) Type-sequence: 1,3 Eigenvalues: i\/—5-, -I_-\/_5_ i (2 +./'—"5'), i (2 -./—5') APPENDIX B COUNTS OF SELF-COMPLEMENTARY GRAPHS We have seen that self—complementary graphs exist having n points for all positive n E 0 or 1(mod 4). The exact number, En’ of self—complementary graphs having n points was given in 1963 by Read [4]. If n = 4N then s l S N where R = 2; kSISksrl) + 4 E kakB'dm3B), s=l 1Sd