UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Computer generation of regular graphs Bowman, Diane M. 1974

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1974_A6_7 B69.pdf [ 4.67MB ]
Metadata
JSON: 831-1.0051754.json
JSON-LD: 831-1.0051754-ld.json
RDF/XML (Pretty): 831-1.0051754-rdf.xml
RDF/JSON: 831-1.0051754-rdf.json
Turtle: 831-1.0051754-turtle.txt
N-Triples: 831-1.0051754-rdf-ntriples.txt
Original Record: 831-1.0051754-source.json
Full Text
831-1.0051754-fulltext.txt
Citation
831-1.0051754.ris

Full Text

COMPUTER GENERATION OF REGULAR GRAPHS by Diane M. Bowman Hon. B . S c , U n i v e r s i t y of Western Ontario, 1972 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of Computer Science Be accept t h i s t h e s i s as conforming to the requ i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l 1974 In p resent ing t h i s t h e s i s in p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e fo r reference and study. I f u r t h e r agree tha t permiss ion for e x t e n s i v e copying of t h i s t h e s i s fo r s c h o l a r l y purposes may be granted by the Head of my Department o r by h i s r e p r e s e n t a t i v e s . It i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l ga in s h a l l not be a l lowed without my w r i t t e n p e r m i s s i o n . Department of \^Q**po\er ^ C \ ^ " C & The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada Date Afif"s\ a°[ , \ci7cf i i ABSTRACT The f o l l o w i n g i s a study of the problem of computer generation of non-isomorphic r e g u l a r graphs of degree d on n p o i n t s . The uork c o n s i s t s of a study of va r i o u s p r o p e r t i e s and r e p r e s e n t a t i o n s of r e g u l a r graphs and a d i s c u s s i o n of hov these might be u s e f u l i n s o l v i n g the isomorphism problem i n the computer generation of r e g u l a r graphs. An a l g o r i t h m f o r the generation of re g u l a r graphs of degree 3 on n p o i n t s with a Hamiltonian c y c l e i s presented. The algorithm i s not i d e a l i n that i t does not generate d i s t i n c t ( i e . non-isomorphic) co p i e s , and so a procedure f o r d e t e c t i n g graph isomorphism i s used to process the l i s t of graphs produced by the algorithm. TABLE OF CONTENTS i i i PAGE INTRODUCTION 1 CHAPTER I PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.0 Int r o d u c t i o n 3 1.1 D e f i n i t i o n s and Notation 3 1.2 The Graph Isomorphism Problem 7 1.3 Known P r o p e r t i e s of Regular Graphs 13 1.4 Computer Generation of Graphs 19 1.5 I z b i c k i ' s Algorithm 19 CHAPTER I I REPRESENTATIONS OF REGULAR GRAPHS 8 GENERATION METHODS 2.0 I n t r o d u c t i o n 25 2.1 Improvements to I z b i c k i ' s Method 25 2.2 Representation as the Sum of Permutation Matrices 27 2.3 Canonical 2 - F a c t o r i z a t i o n 36 2.1 A Dead-End I n v e s t i g a t i o n 40 CHAPTER I I I GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 42 3.1 F o r m a l i z a t i o n of the Algorithm 49 3.2 Hamiltonian Cubic Graphs Generated 52 3.3 Order of the Computation 53 3.4 Comments on the Computer Program 55 3.5 Conclusion 55 BIBLIOGRAPHY 57 APPENDIX I The Computer Program 60 APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,12 P t s . 74 LIST OF TABLES i v PAGE TABLE I R e s u l t s of Generation Algorithm 52 LIST OF FIGURES V FIGURE PAGE 1.1 A Cubic Graph with no 1-Factor 13 1.2 Petersen Graph 15 1.3 S p l i t t i n g of an edge h 17 1.4 An X-extension 17 1.5 G* 18 1.6 Basis f o r 8-Point Cubic Graphs 23 2.1 A P a i r of 4-Point Graphs 25 2.2 Two 4-Point Graphs 26 2.3 A 6-Point Cubic Graph 30 2.4 Representation of an 8-Point Graph 32 2.5 A Regular Graph of Even Degree 35 2.6 2 - F a c t o r i z a t i o n s of 8-Point Graphs 39 3.1 I n i t i a l Cases f o r 8-Point Graphs 43 3.2 Case (i) For 8-Points 45 3.3 Case ( i i ) For 8-Points 45 3.4 Case ( i i i ) For 8-Points 46 3.5 Two Isomorphic 8-Point Graphs 46 3.6 Two Isomorphic 8-Point Graphs 48 3.7 Three 8-Point Graphs 48 ACKNOWLEDGMENT v i I would l i k e to express my sincere appreciation to Dr. Abbe Mowshowitz for his many helpful ideas during the course of the research and for h i s talented assistance i n editing of the the s i s . I would also l i k e to thank Dr. J. Kennedy for his helpful suggestions. Fin a n c i a l assistance was g r a t e f u l l y received from the National Research Council of Canada and the Department of Computer Science. INTRODUCTION 1 The f o l l o w i n g i s a study of the problem of computer generation of non-isomorphic r e g u l a r graphs of degree d on n p o i n t s . The choice of r e g u l a r graphs does not s i g n i f i c a n t l y r e s t r i c t the generation problem, because the r e g u l a r subgraphs of a graph play a c e n t r a l r o l e i n determining isomorphism. Since isomorphism determination dominates the computation time i n a graph generation process, the v a r i o u s p r o p e r t i e s and r e p r e s e n t a t i o n s of r e g u l a r graphs are examined to minimize the number of isomorphic graphs generated. However, i t becomes c l e a r that r e s t r i c t i n g the generation to r e g u l a r graphs does not s i g n i f i c a n t l y reduce the complexity of the general problem. In view of t h i s , we narrow down the problem t o Hamiltonian cubic graphs. An algorithm f o r the generation of Hamiltonian cubic graphs i s developed. The algorithm i s not i d e a l i n that i t does not generate d i s t i n c t ( i e . non-isomorphic) c o p i e s , and so a procedure f o r determining graph isomorphism i s used to process the l i s t of graphs produced by the algorithm. In Chapter I , various approaches to the isomorphism problem are reviewed with an i n d i c a t i o n of t h e i r a p p l i c a b i l i t y to the case of r e g u l a r graphs. In a d d i t i o n , a survey of the known p r o p e r t i e s of r e g u l a r graphs r e l e v a n t to t h e i r generation i s presented as background i n f o r m a t i o n to the problem. F i n a l l y , a d i s c u s s i o n of I z b i c k i ' s [23] proposed methods f o r generation of r e g u l a r graphs i s given. In Chapter I I , s e v e r a l d i f f e r e n t approaches to the problem of generating regular graphs are presented along with some INTRODUCTION 2 re s u l t s discovered in the search f o r a fe a s i b l e solution. In Chapter III, an algorithm f o r the generation of Hamiltonian cubic graphs i s presented. The number of graphs on 6, 8, 10, and 12 points as produced by a computer implementation of the algorithm are given along with the number of rep e t i t i o n s in each case. I: PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 3 1.0 Introduction In t h i s Chapter, various approaches to the isomorphism problem are reviewed with an i n d i c a t i o n of t h e i r a p p l i c a b i l i t y to the case of regular graphs. In addition, a survey of the known properties of regular graphs relevant to their generation i s presented as background information to the problem. F i n a l l y , a discussion of I z b i c k i ' s [23] proposed methods for generation of regular graphs i s given. 1.1 D e f i n i t i o n s and Notation The notation adopted i n t h i s thesis i s l a r g e l y that of Harary [17]. Definitions needed for the whole discussion are given i n t h i s section; others w i l l be introduced as necessary. a SEJlEh G= (V,E) i s a f i n i t e non-empty set V=V (G) with a c o l l e c t i o n E=E (G) of unordered pairs of d i s t i n c t elements of V(G). The elements of V are c a l l e d the points (or vertices ) of G. Each pair uv=[u,v} i n E (G) i s c a l l e d a l i n e (or edge ) of G and the given points u,v i n V(G) are said to be adjacent. Clearly, t h i s type of graph i s what some authors c a l l f i n i t e , undirected, with no loops and no p a r a l l e l edges. A point u i n V (G) i s incident with a l i n e x in E(G) i f x=uv for some u,v i n V(G). The complement G of a graph G on n points has V(G)=V(G) as i t s set of points; the set of edges E (G) i s determined as I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 4 1.1 D e f i n i t i o n s and Notation f o l l o w s : l e t E*(G) be the set of a l l p o s s i b l e unordered p a i r s of d i s t i n c t p o i n t s of V (G), then E (G) = E* (G)-E (G). A graph H i s c a l l e d a subgraph of a graph G i f V (H)£V (G)and E(H)CE(G) such t h a t every x i n E(H) i s i n c i d e n t with a poi n t i n V(H). A subgraph H of a graph G i s c a l l e d a spanning subgraph i f i t contains a l l the nodes of G. The order of a set A i s i t s c a r d i n a l i t y (denoted |A|); the order of a graph G i s the order of i t s set of p o i n t s . A walk of a graph G i s an a l t e r n a t i n g sequence of p o i n t s and l i n e s v c ,x, , v, ,.... , v O M ,x f t, vft , beginning and ending with p o i n t s of V(G), i n which each l i n e i s i n c i d e n t with the two points immediately preceding and f o l l o w i n g i t . This walk j o i n s v 0 and Vf> and i s sometimes c a l l e d a v 0-v f t walk. I t i s closed i f v 0=v f t and i s open otherwise. I t i s a t r a i l i f a l l the l i n e s are d i s t i n c t , and a path i f a l l the p o i n t s (and n e c e s s a r i l y a l l the l i n e s ) are d i s t i n c t . I f the walk i s c l o s e d , then i t i s a cjgcle provided i t s n p o i n t s are d i s t i n c t and n>3 (sometimes denoted an n - c y c l e ) . An n-cycle of a graph G i s c a l l e d a Hamiltonian eyele i f |V{G)|=n. The airth °f a graph G i s the length of a s h o r t e s t c y c l e i n G. A graph G i s connected i f every p a i r of p o i n t s i n V(G) are joined by a path formed from members of E (G). A maximal connected subgraph of G i s c a l l e d a component of G. A bridge i s I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1 . 1 D e f i n i t i o n s and Notation 5 a l i n e whose removal incre a s e s the number of components. A l3i®IliJB3 f of a graph G with n p o i n t s i s a b i j e c t i o n of an n-element set to V (G). A graph G together with a l a b e l l i n g f* i s s a i d to be l a b e l e d . Be w i l l use the s e t of l a b e l s to represent V (G) . Let G be a l a b e l e d graph with v e r t i c e s v,,v x, ,v n. The adjacency matrix A(G)=[aj^] of G i s an n x n binary matrix i n which a - = 1 i f v^ i s adjacent to v. and a- =0 otherwise. An homomor^hism of a graph G to a graph H i s a s u r j e c t i o n f of V(G) to V (H) which preserves adjacencies. i . e . , x=uv i s i n E(G) i f f f (x)=f (u) f (v) i s i n E (H) . Two graphs G and H are s a i d to be homomprphic i f there e x i s t s an homorphism between them. An isomorphism of a graph G t o a graph H i s a b i j e c t i o n h of V(G) onto V(H) which preserves adjacencies. Two graphs G and H are s a i d to be isomorphic i f there e x i s t s an isomorphism between them. An automorphism of a labeled graph G i s an isomorphism of G to i t s e l f . I t i s easy t o see that an automorphism may be regarded as a permutation of the s e t of l a b e l s which preserves adjacencies. Moreover, i t i s t r i v i a l to v e r i f y that the c o l l e c t i o n of automorphisms of G (denoted P ) forms a group c a l l e d the automorphism of G. The automorphism E§Eiiti2SiJL3 °^ a 9^aph G i s the c o l l e c t i o n of o r b i t s of i t s I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1 . 1 D e f i n i t i o n s and Notation 6 automorphism group. The degree of a point v of G denoted deg v i s the number of l i n e s i n E (G) i n c i d e n t with v. A graph G i s r e g u l a r of degree d i f a l l p o i n t s i n V (G) are of degree d. A n n - f a c t o r of a graph G i s a spanning subgraph that i s re g u l a r of degree n. A graph G i s the sum of n - f a c t o r s i f i t i s t h e i r l i n e - d i s j o i n t union. A graph G has an n - f a c t o r i z a t i o n i f G i s the sum of n - f a c t o r s . Let V(G)={v, , v i # #vrt} be the set of p o i n t s of a graph G. Let D=(d,,d l, , d„) where each d^ i s the degree of point v^. Rename the elements of D so tha t d,<d a<——5d n. The n-tuple D i s then c a l l e d the degree seguence of the graph G. An edge of a graph G w i l l be c a l l e d a d j o i n t to a subgraph H i f one of i t s endpoints belongs to the subgraph H and the other does not. The a d j o i n t number of a subgraph i s the number of edges a d j o i n t to that subgraph. A subgraph, H of G i s a t r a n s i t i v e subgraph of G i f f o r any two nodes, x and y of H there e x i s t s an automorphism of G mapping x onto y. I: PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.2 The Graph Isomorphism Problem 7 I n the computer generation of regular graphs i t i s an important fe a t u r e of the algorithm to generate the graphs u i t h minimal r e p e t i t i o n . I d e a l l y , the algorithm would generate non-isomorphic copies. However, f a l l i n g short of the i d e a l , we need an e f f i c i e n t graph isomorphism algorithm to e l i m i n a t e the r e p e t i t i o n s . The graph isomorphism problem i s to determine whether or not two a r b i t r a r y graphs G and H are isomorphic. As yet, there i s no known e f f i c i e n t d e t e r m i n i s t i c algorithm f o r determining whether two graphs are isomorphic. By an e f f i c i e n t d e t e r m i n i s t i c algorithm, we mean an algorithm which guarantees a s o l u t i o n i n time T, where T i s p r o p o r t i o n a l t o a constant power of n, the number of points of the graph. For graphs of order n whose points are l a b e l e d with the same set of elements, there i s an i n e f f i c i e n t d e t e r m i n i s t i c isomorphism algorithm based upon S n the s e t of a l l n! permutations on n po i n t s . Each element of S n i s used to permute the p o i n t s of a graph G, and then a t e s t i s made to see i f t h i s i s i d e n t i c a l to a given graph H. I f the two graphs are i d e n t i c a l then the process terminates. I f the graphs are not i d e n t i c a l then the next element of Srt i s used. Thus, t h i s algorithm always y i e l d s a s o l u t i o n ; however, the number of i t e r a t i o n s f o r a given graph i s bounded by n!. Even on modern high-speed computers the computation time and memory I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.2 The Graph Isomorphism Problem 8 requirements f o r such an algorithm are excessive. One p a r t i c u l a r r e a l i z a t i o n of t h i s a l g o r i t h m i s obtained using a r e p r e s e n t a t i o n of graphs which d e r i v e s from Polya's theory of enumeration (see Harary [ 1 "7 ] ) . Let D={ [ i , j ] I 1<i<j<n} ana l e t R = { 0 , 1 } . A l a b e l e d graph G may be expressed as a f u n c t i o n f which maps D i n t o R as f o l l o w s . I f [ i , j ] i n D i s a l i n e of G, then f ( [ i # j ] ) = 1 otherwise f ( [ i , j ] ) = 0. Thus a l l p o s s i b l e graphs on n p o i n t s may be represented as {f|f:D-»R}. For n=4 and D = { 1 2 , 1 3 , 1 4 , 2 3 , 2 4 , 3 4 } the f u n c t i o n s are of the form: 'K* ^ "J-** °L« \*»We ^ 1 € c O t M The f u n c t i o n f K maps [ i , j ] i n D i n t o 1 i f i i s adjacent to j i n the corresponding graph. Note than any permutation C> i n S n induces a permutation s' on D. Thus using Polya's notion of equivalence we have that two fu n c t i o n s (graphs) f, and f a are equivalent (isomorphic) i f there e x i s t s S" i n Srt such that f , (d) =f x ( <s'(d)) f o r a l l d i n D where i s the permutation on D induced by <S" . A r e g u l a r graph G on n p o i n t s of degree d may be represented as a f u n c t i o n f:D-*R. Let D be the set of ordered p a i r s of d i s t i n c t i n t e g e r s from { 1 , 2 , ,n} and l e t R - { 0 , 1 } . Let P={p,/PjLr * PK ^ **e t^ i e s e t o f P a i r s ^ n D that are I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 9 1.2 The Graph Isomorphism Problem mapped by f i n t o 1. A f u n c t i o n f:D—*R represents a r e g u l a r graph G on n po i n t s of degree d i f each element of {1,2, ,n} occurs among the p a i r s of P e x a c t l y d times. Unfortunately, t h i s r e p r e s e n t a t i o n of r e g u l a r graphs o f f e r s l i t t l e to reduce the problem space. The implementation of t h i s approach on the computer i s improved by various h e u r i s t i c procedures t o reduce the maximum number of permutations to be examined to determine isomorphism. One o p t i m i z a t i o n technique i s to consider the degree sequence of the graph G. Thus a graph could be isomorphic only to those graphs with the same degree sequence. As w e l l , when co n s i d e r i n g two graphs G and H of the same degree sequence, a point of G could be mapped only onto those p o i n t s of H of the same degree. So i n t h i s fashion the number of p o s s i b i l i t i e s i s g r e a t l y reduced. However, t h i s c r i t e r i o n i s obviously of l i t t l e use i n the case of r e g u l a r graphs. Another property which i s u s e f u l i n reducing the problem space i s the c y c l e s t r u c t u r e of the graph. Frucht [13] introduced the notion of type of a vertex to capture t h i s property. Let vertex v of a graph G have degree d. Let P={p, ,P a, #Pj} be the set of a l l p o i n t s i n V (G) t h a t are adjacent to v. Consider a l l p o s s i b l e unordered p a i r s of d i s t i n c t elements from the s e t P={ p, p^ ,p, p 3 , *PX P, » ' ^ d i ^ c i ^ * Let the set U={u,,u 1,-—*^ s} b e i n 1-1 correspondence with the I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1 . 2 The Graph Isomorphism Problem 10 set P. For each p a i r p^p. i n P, set the corresponding u K equal s i to the s i z e of the sm a l l e s t c y c l e c o n t a i n i n g both edges vp^ and vp-. I f there i s no c y c l e c o n t a i n i n g those edges then set uK=<=o. L e x i c o g r a p h i c a l l y order U so that u 4 < U a . < - ^ u s . Then the s-tuple ( u , , u l f ,u s) i s c a l l e d the type of the vertex v. Thus i n t r y i n g to determine isomorphism, only v e r t i c e s of the same type may be mapped i n t o one another. This idea i s p a r t i c u l a r l y v aluable i n connection with r e g u l a r graphs s i n c e the degree sequence property i s of no use. However, the computation r e q u i r e d to determine the type i n t h i s f a s h ion i s n o n - t r i v i a l . Another approach to the graph isomorphism problem i s provided by rook polynomials (see f o r example, Riordan [33]). B a s i c a l l y these polynomials are ass o c i a t e d with the enumeration of permutations s a t i s f y i n g p r e s c r i b e d s e t s of r e s t r i c t i o n s on the elements permuted. Any permutation with r e s t r i c t e d p o s i t i o n s can be represented on an nxn board and has a rook polynomial a s s o c i a t e d with i t . Each nxn board corresponds to the adjacency matrix of an nxn graph ( i f loops are allowed). Without going i n t o the d e t a i l s , there are c e r t a i n equivalence c o n d i t i o n s which make some of the boards the same. This idea of equiv a l e n t boards i s not e x a c t l y the same as isomorphic adjacency matrices but i t does capture the same s o r t of notion. Riordan r e p o r t s that Kaplansky has proved some c o n d i t i o n s f o r I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 11 1.2 The Graph Isomorphism Problem two polynomials to be equivalent and the analogous r e s u l t s are true f o r isomorphic graphs. I t would be d e s i r a b l e to be able to compute the rook polynomials of the adjacency matrices of two graphs and then decide whether or not the graphs are isomorphic based on the p r o p e r t i e s of the polynomials. C o r n e i l and G o t l i e b [8,9] have developed an e f f i c i e n t method f o r determining whether two graphs are isomorphic. However, t h e i r method i s based upon a c o n j e c t u r e , and so i t i s not d e t e r m i n i s t i c . I t terminates with one of the f o l l o w i n g three statements: (i) the graphs are isomorphic ( i i ) the graphs are not isomorphic ( i i i ) the graphs form a counterexample to the conjecture As yet, no counterexamples have been discovered. For any given graph, the procedure deri v e s two graphs, the r e p r e s e n t a t i v e graph and the reordered graph. The re p r e s e n t a t i v e graph i s a homomorphic image of the o r i g i n a l graph, and the reordered graph i s constructed from the r e p r e s e n t a t i v e graph to be isomorphic to the given graph. The method assigns unique l a b e l s to the v e r t i c e s of both derived graphs. Thus, two reordered graphs are isomorphic i f f they are i d e n t i c a l . C o r n e i l and G o t l i e b give a conjecture that s t a t e s that the r e p r e s e n t a t i v e graphs e x h i b i t the automorphism p a r t i t i o n i n g of the given graph. Thus, i f the r e p r e s e n t a t i v e I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.2 The Graph Isomorphism Problem 12 graphs are not i d e n t i c a l then the given graphs are not isomorphic. A l s o , the authors show that i f the reordered graphs are i d e n t i c a l , then the given graphs are isomorphic. The order of the computation f o r t h i s algorithm i s s i g n i f i c a n t l y b e t t e r than the n! bound imposed by the method that t e s t s a l l permutations i n S n. For graphs on n po i n t s t h a t do not contain a 2 - s t r o n g l y r e g u l a r t r a n s i t i v e subgraph ([9,p.53]) the upper bound f o r the computation i s cn 5 where c i s a constant. For graphs on n p o i n t s that do c o n t a i n a t r a n s i t i v e h-strongly r e g u l a r subgraph, the upper bound f o r the computation depends on n5*^!. Since n i s the upper bound f o r h, the algorithm i s i n e f f i c i e n t f o r t h i s c l a s s of graphs; otherwise i t i s e f f i c i e n t . I: PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.3 Known P r o p e r t i e s of Regular Graphs 13 In t h i s s e c t i o n we w i l l review p r o p e r t i e s of r e g u l a r graphs that r e l a t e t o t h e i r s t r u c t u r e i n order to i n d i c a t e the l i m i t e d realm of knowledge r e l e v a n t t o t h e i r generation. As w i l l be seen l a t e r , the notion of f a c t o r i z a t i o n i s u s e f u l i n the generation process. I t turns out that the f a c t o r s of a graph provide a frame of reference w i t h i n which isomorphism can be examined. Thus we w i l l examine what i s known about f a c t o r s of r e g u l a r graphs. Petersen [29] e s t a b l i s h e d some important r e s u l t s about the f a c t o r s of r e g u l a r graphs. In p a r t i c u l a r , he showed that a connected graph i s 2 - f a c t o r a b l e i f f i t i s r e g u l a r of even degree; and i f a cubic graph contains a 1-factor then i t must als o have a 2 - f a c t o r . In a d d i t i o n , Petersen proved that any cubic graph without a 1-factor must have a bridge (see Figure 1 . 1 ) , and every b r i d g e l e s s c u b i c graph i s the sum of a 1 - f a c t o r and a 2 - f a c t o r . Figure 1.1 A cubic graph with no 1-factor I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 14 1.3 Known P r o p e r t i e s of Regular Graphs The famous Petersen graph i n Figure 1.2 i l l u s t r a t e s that t h i s l a s t r e s u l t cannot be strengthened t o the sum of three 1-f a c t o r s . 1 .• Figure 1.2 Petersen graph Baebler [ 1 ] extended Petersen's r e s u l t s by showing t h a t a f i n i t e graph of degree 2m+1 has a f a c t o r of degree 2q, i f i t has no proper subgraph whose a d j o i n t number i s l e s s than 2q. This gives a c o n d i t i o n f o r the exist e n c e of f a c t o r s of odd degree, and f o r g=m i t i s a c o n d i t i o n f o r the existence of a f a c t o r of degree 1. Rado [30] g i v e s a necessary and s u f f i c i e n t c o n d i t i o n f o r the e x i s t e n c e of f a c t o r s of degree 1 i n even ( a l l c y c l e s of even length) graphs. G a l l a i [14] e s t a b l i s h e s the f o l l o w i n g two r e s u l t s . Denote by ^ the minimum of the a d j o i n t numbers of those proper subgraphs of the graph which c o n t a i n an odd number of p o i n t s . A coherent graph i s one which has ^ >1. (1) A coherent r e g u l a r f i n i t e graph of degree v=s+t can be decomposed i n t o the product of f a c t o r s of degree s and of degree I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.3 Known P r o p e r t i e s of Regular Graphs 15 t , i f the a d j o i n t numbers of i t s proper subgraphs c o n t a i n i n g an odd number of points exceed or equal the greater of the numbers v/s and v / t ; provided t h a t whenever both s and t are odd, the graph has an even number of p o i n t s . (2) I f a r e g u l a r graph of odd degree v has no bridge ( £ >1), then i t always has a f a c t o r of any even degree not exceeding consequently a l s o a f a c t o r of any odd degree not l e s s than Two r e s u l t s of Konig ( r e f e r r e d to by G a l l a i ) are a l s o of i n t e r e s t here. (1) A r e g u l a r graph of even degree v with an even number of points always possesses a f a c t o r of degree v/2. (2) A r e g u l a r graph of even degree possesses a f a c t o r of any degree not exceeding the degree of the graph. Some other r e s u l t s are known about the f a c t o r s of a graph, but i n the author's opinion these do not seem u s e f u l f o r graph generation. Lovasz [28] e s t a b l i s h e s various r e s u l t s about the s t r u c t u r e of graphs that contain a 1- f a c t o r . Tutte [38] gives a necessary and s u f f i c i e n t c o n d i t i o n that a given l o c a l l y f i n i t e graph has an n- f a c t o r where n i s any p o s i t i v e i n t e g e r . I t would appear that a study of the automorphism groups of reg u l a r graphs could lead to i n s i g h t s i n t o the generation of non-isomorphic copies. Frucht»s [13] r e s u l t s f o r cub i c graphs I: PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.3 Known P r o p e r t i e s of Regular Graphs 16 i l l u s t r a t e the general case. He addresses the problem of c o n s t r u c t i n g a cubic graph whose automorphism group i s isomorphic t o a given a b s t r a c t group. In order to e s t a b l i s h h i s r e s u l t s , Frucht uses the notion of type of a graph (as explained p r e v i o u s l y ) . In p a r t i c u l a r he shows t h a t : (1) A necessary (but not s u f f i c i e n t ) c o n d i t i o n that a vertex u of a cubic graph may be mapped i n t o a vertex v by an automorphism of the graph i s that u and v are of the same type. (2) I f f o r some 3 numbers K < h </K there i s i n a cubic graph j u s t one vertex u of the type (}<»/\»>lO then u i s l e f t f i x e d by each permutation belonging to the group of the graph. These two observations concerning the notion of type prove to be guite u s e f u l i n t e s t i n g f o r isomorphism between r e g u l a r graphs. Anton Kotzig [25] e s t a b l i s h e s some s t r u c t u r a l r e s u l t s which i n d i c a t e how to con s t r u c t bichromatic ( a l l c y c l e s of even length) r e g u l a r graphs of degree three. He de f i n e s the s p l i t t i n g of an edge h tha t j o i n s v e r t i c e s u and v of a graph G to generate two graphs G* and G" as demonstrated i n Figure 1.3. I: PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.3 Known P r o p e r t i e s of Regular Graphs 17 G: O -G: V> o-O a « v « i % d e n o t e (Nodes o"£ c o l o u r s x a ^ d \j respectively Figure 1.3 S p l i t t i n g of an Edge h An edge h of a graph G i s c a l l e d X-reducible i f at l e a s t one of the graphs a r i s i n g from the s p l i t t i n g of h does not con t a i n m u l t i p l e edges; i f a l l the graphs contain m u l t i p l e edges then h i s X - i r r e d u c i b l e . A r e g u l a r graph of the t h i r d degree i s X - i r r e d u c i b l e i f each of i t s edges i s X - i r r e d u c i b l e . A graph G* i s an X-extension of a graph G on the edges g, h i f G» a r i s e s from G as shown below i n Figure 1.4. 6 c 6 a Figure 1.4 An X-extension I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.3 Known P r o p e r t i e s of Regular Graphs 18 K o t z i g proves the f o l l o w i n g s t r u c t u r a l r e s u l t s : (1) Each component of an X - i r r e d u c i b l e graph i s isomorphic to the graph G* shown i n Figure 1.5. Figure 1.5 G* (2) Any bichromatic r e g u l a r graph of the t h i r d degree with 2n v e r t i c e s without m u l t i p l e edges i s e i t h e r X - i r r e d u c i b l e or i t may be constructed by repeated X-extensions from a c e r t a i n X-i r r e d u c i b l e graph with m components, which are a l l isomorphic to the graph G*, where 6m<2n. Unfortunately, t h i s r e s u l t i s very s p e c i f i c t o bichromatic r e g u l a r graphs and so we cannot extend i t t o a more general c l a s s of r e g u l a r graphs. I z b i c k i [21,22], Sauer [ 3 6 ] , Brown [ 5 ] , Benson [ 3 ] , have e s t a b l i s h e d d i f f e r e n t s p e c i f i c r e s u l t s about regular graphs r e l a t i n g t o automorphism group, c o n n e c t i v i t y , c o l o r i n g number, and g i r t h , but here again the r e s u l t s are too s p e c i a l i z e d t o be valuable f o r graph generation. I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.4 Computer Generation of Graphs 19 In order to avoid e r r o r s , the a s s i s t a n c e of a computer i s e s s e n t i a l i n the generation of graphs. Because of the great amount of storage and CPU time r e q u i r e d when the graphs become l a r g e , t h i s problem presents an i n t e r e s t i n g challenge to the best of computer r e p r e s e n t a t i o n methods, s o r t i n g techniques, and i n f o r m a t i o n r e p r e s e n t a t i o n . Various ideas f o r computer manipulation of graphs and c o m b i n a t o r i a l e n t i t i e s such as permutations, s i g n a t u r e s , e t c . may be found i n references such as Heap [ 1 9 ] , Read [ 3 2 ] , H e l l s [ 4 0 ] , Lehmer [ 2 6 ] , and H a l l & Knuth [ 1 6 ] . The computer techniques used to generate c u b i c graphs with a Hamiltonian c i r c u i t w i l l be discussed i n Chapter 3 a f t e r p r e s e n t a t i o n of the algorithm. 1.5 I z b i c k i ' s Algorithm H. I z b i c k i [23] presents an algorithm f o r computer generation of r e g u l a r graphs. In the f i r s t part of h i s paper he discusses a r a t h e r crude method f o r generating a l l r e g u l a r graphs on n points. Since the adjacency matrix of a graph i s symmetric then there are 5; p o s i t i o n s i n the matrix to be set to 0 or 1. Thus there i s an upper bound of 2 binary numbers to be considered. This can be reduced t o 2 * binary numbers by s u b t r a c t i n g a vertex from the graph and l e a v i n g d v e r t i c e s of degree d-1 and n-d-1 v e r t i c e s of degree d. The algorithm would then count i n binary from 0 to 2 a- and I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 20 1.5 I z b i c k i ' s Algorithm examine the corresponding adjacency matrix to see i f i t i s a r e g u l a r graph. This algorithm i s very slow and as w e l l , i t produces the maximum number of r e p e t i t i o n s . (Note t h a t f o r 8 point graphs, i t would have to count to 2*"'.) I z b i c k i i ntroduces an a l t e r n a t i v e method i n order to reduce the computation time. Let X be a r e g u l a r graph of degree d on n p o i n t s . One can p a r t i t i o n the s e t V(X) i n t o two c l a s s e s V,(X) and V x (X) where |V,(X)|=n, and |V a(X)|=n x, and n,+nx=n. Without l o s s of g e n e r a l i t y , one can define V, (X) = {v^ i n V (X) |i=1, ,n,} and V a(X) = {vx i n V (X) ji=n,+1, ,n}. From t h i s p a r t i t i o n i n g of V(X) one can define three graphs Y, , Y^, Y 3 i n the f o l l o w i n g way: V(Y,)=V, (X) E(Y,)=[[v i,v. ]|[ v x,v^ ] i n E(X); v. ,v. i n V, (X) } V(YJ=V a(X) E( ^ ) = { [ v x , v - 3 1 1 ; ^ , v . ] i n E(X); v ^ v . i n V X(X)} V(Y 3)=V(X) E(Y 3)={[v J L,v i ] | [ V j t ,v^ ] i n E(X); v ; i n V, (X) ; v- i n } and thus E(X)=E(Y, )+E(Y : i)+E(Y 3) Hence one has p a r t i t i o n e d the adjacency matrix M of the graph X i n the f o l l o w i n g way: I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.5 I z b i c k i ' s Algorithm ( A , where M., M_, and [ ^ T ^ 3 ] are the adjacency matrices of the graphs Y,, Y x, and Y 3 r e s p e c t i v e l y . Observe that 21 E (X) | f>». Q>. 2 | E (Y,) | = 2 2 ru n |E(Y 3)|= 2, l i t 'i:f>,+» and so |E(Y 3) |=n,d-2|E(Y,) | |E(Y ) | = n : ud-2|E(Y a) | n , a-2|B(Y,) |=n x a-2|E(YJ | I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 1.5 I z b i c k i ' s Algorithm 22 (n,-n x)d=2{|E(Y,) |-|E(Y X) |) I f n,=nl then | E (Y, ) |= | E (X a) | otherwise, d=2 (|E (Y, ) | - | E ( Y X ) I ) . n, - r\ x I z b i c k i proposes to use these r e s u l t s i n the generation of regu l a r graphs on an even number of po i n t s . Let n,=n1=n/2. From the l i s t of a l l graphs on n/2 p o i n t s , s e l e c t p a i r s of graphs Y, and Y x such th a t | E (Y,) |= | E (Y a) | (Y, may equal Y a) and use these to form a l l the p o s s i b l e graphs Y 3 to c o n s t r u c t a re g u l a r graph X. The second method proposed by I z b i c k i i s indeed much sh o r t e r than the f i r s t , but i t does not contend with the bas i c problem of l a r g e s c a l e r e p e t i t i o n of isomorphic copies of the same graph. For purposes of comparison l a t e r , consider I z b i c k i ' s improved method f o r r e g u l a r graphs of degree 3 on 8 p o i n t s . The method would combine the f o l l o w i n g p a i r s of graphs on 4 p o i n t s with the same number of l i n e s : Figure 1.6 B a s i s f o r 8-Point Cubic Graphs I : PROPERTIES OF REGULAR GRAPHS RELEVANT TO GENERATION 24 1.5 I z b i c k i ' s Algorithm The f i r s t and second cases y i e l d 24 graphs each and the t h i r d case y i e l d s 90 graphs. So at the end of the computation there would be a few hundred graphs produced. In a c t u a l i t y , there are 6 non-isomorphic graphs of degree 3 on 8 p o i n t s . In Chapter I I of t h i s work, a m o d i f i c a t i o n of I z b i c k i ' s method i s proposed which reduces the number of p o s s i b i l i t i e s , I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 25 2.0 I n t r o d u c t i o n I n t h i s Chapter we w i l l i n v e s t i g a t e s e v e r a l d i f f e r e n t approaches t o the problem of generating r e g u l a r graphs, a l l of which are promising but have s e r i o u s drawbacks. Our aim here i s twofold: to r e v e a l the weaknesses of c e r t a i n p a r t i a l s o l u t i o n s , and t o present some r e s u l t s discovered i n the search f o r a f e a s i b l e s o l u t i o n . The shortcomings of c e r t a i n apparently n a t u r a l approaches h i g h l i g h t the d i f f i c u l t y of the problem, and thus help to j u s t i f y our narrowing of the problem space i n Chapter I I I to Hamiltonian cubic graphs. 2.1 Improvements t o I z b i c k i ' s Method I z b i c k i [23] generates r e g u l a r graphs by c o n s t r u c t i n g a l l p o s s i b i l i t i e s from p a i r s of graphs with an equal number of l i n e s (as explained i n s e c t i o n 1.5). The p a i r of graphs i n Figure 2.1 would be used i n t h i s method to generate some of the 8-point graphs of degree 3. Figure 2.1 A P a i r of 4-Point Graphs I I : REPRESENTATIONS OF REGULAR GRAPHS B GENERATION METHODS 26 2.1 Improvements t o I z b i c k i 1 s Method The f i r s t improvement t o I z b i c k i 1 s method would be to consider symmetry of the graphs as much as p o s s i b l e i n p l a c i n g p r o s pective adjacencies. For example, suppose we s t a r t with node 1. I t may be adjacent t o any two of [5,7,8} g i v i n g three p o s s i b i l i t i e s a l l of which w i l l y i e l d the same intermediate graphs. S i m i l a r i l y symmetry arguments may be a p p l i e d t o a l i m i t e d extent f o r the other nodes. The second improvement i n v o l v e s f i n d i n g adjacencies f o r the node of the l e a s t degree f i r s t . For example consider the p a i r shown i n Fig u r e 2.2. I f we f i n d adjacencies f o r node 3 f i r s t , then node 3 must be adjacent to each of 5 ,7, and 8 and there i s no other choice f o r node 3. However, i f we had considered nodes 1 and 4 f i r s t then i t might have led to dead end choices where node 3 could not have degree 3. I t i s c l e a r t h a t by f i l l i n g i n the nodes of greatest need f i r s t , the number of choices i s reduced. 5 I Figure 2.2 Two 4-Point Graphs I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 27 2.2 Representation as the Sum of Permutation Matrices The adjacency matrix of a r e g u l a r graph may be expressed as a sum of permutation matrices. The s i m p l i c i t y of permutation matrices makes t h i s r e p r e s e n t a t i o n a n a t u r a l one to consider. More p r e c i s e l y , a permutation matrix of order n i s a (0,1)-matrix with a s i n g l e entry 1 i n each row and column and a l l other e n t r i e s are 0. Now, suppose A i s a (0, 1)-matrix of order n such that each row and column sum of A i s equal to the p o s i t i v e i n t e g e r k. Then (see, f o r example, Ryser [35]) A=P, +Pa+ +P* where the P x are permutation matrices. Observe that the adjacency matrix A(G) of a regular graph G of degree d on n p o i n t s , i s a (0,1)-matrix of order n such t h a t each row and column sum i s equal t o the p o s i t i v e i n t e g e r d. Thus A (G) may be expressed i n the form A (G) =P, +Pa + +PJ where the P^ are permutation matrices. In what f o l l o w s we w i l l regard these nxn permutation matrices interchangeably with permutations on n p o i n t s . For example, the matrix o o \ o \ 0 o o \o O O I / corresponds t o the 1-permutation [ 1 2- 2> 4-In an e f f o r t to f u r t h e r c h a r a c t e r i z e r e g u l a r graphs using these notions we prove the f o l l o w i n g . I I : REPRESENTATIONS OF REGULAR GRAPHS 8 GENERATION METHODS 28 2.2 Representation as the Sum of Permutation Matrices Theorem 1.0 Let G be a reg u l a r graph of degree d on n p o i n t s . Let A(G) = TT, + TTj.+ +TT«I where the Tfl are permutations. Let the matrix U be a dxn matrix whose rows are the n-permutations u-TT, i 1. o • » » 1 x u JJLM — TU TTd \ JW, jUUi Then (1) each column of u c o n s i s t s of d d i s t i n c t elements (2) k does not appear i n the k column of U f o r k=1,—, n (3) each element of the set {1,2, ,n} apears e x a c t l y d times i n the matrix U (U) whenever u^^=h (1<h<n) appears somewhere i n U, then there e x i s t s an element r i n {1,2, ,d} such t h a t up^=k. Proof: (1) Suppose there e x i s t s i n column k (1<k<n) two elements uik' u/mV (i*m a n d i» m a r e i n {1*2, ,d}) such t h a t ujL1<=u^y(=s. Let P^ and P^ be the permutation matrices t h a t correspond to TT-1 TT» t i i e permutations which contain u-, and u . r e s p e c t i v e l y . Since u. =u . then both matrices P. and P w i l l I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 29 2.2 Representation as the Sum of Permutation Matrices have an entry of 1 i n the k row at the s ^ p o s i t i o n . This i m p l i e s that i n the adjacency matrix of G t h e i r sum w i l l equal 2 i n t h i s p o s i t i o n , which i s i m p o s s i b l e . (2) Suppose f o r a given column k (1<k<n) there e x i s t s i i n {1,2, ,d} such t h a t Uj^=k. Let Vj, be the permutation matrix corresponding to the permutation TT^ which contains u^=k. Then P^ has a 1 i n the k row at the k p o s i t i o n of the matrix. This i m p l i e s t h a t A(G) has a non-zero entry i n the k^ ^ row at the k+^ p o s i t i o n . Thus point k of the graph i s adjacent to i t s e l f , which i s i m p o s s i b l e . (3) Suppose an element s i n {1,2,-—,n} appears t times i n U where t#d. I t f o l l o w s from (1) and (2) that (n-1) i s an upper bound f o r t . Hence there e x i s t s t separate columns of U which co n t a i n s and so there e x i s t s t permutation matrices t h a t have an entry of 1 i n the s column. Since these matrices sum to A(G) i t f o l l o w s t h a t the degree of point s i s t , which i s impossible. (U) Suppose u^k=h (1<h<n) (h#k) (1<i<d) appears i n the k*k column of U. Let P^ . be the permutation matrix which corresponds to TTj. , the permutation which contains u j ^ . This i m p l i e s t h a t P^ has an entry 1 i n the k row and the h p o s i t i o n . Thus point k i s adjacent to point h i n G and so p o i n t h i s adjacent I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 30 2.2 Representation as the Sum of Permutation Matrices to point k i n G. Hence there e x i s t s a permutation matrix P r that has a 1 i n the h row a t the k p o s i t i o n , and so i n the corresponding permutation TTr the h"*^  element eguals k i e . u^=k. The example of a s i x p o i n t cubic graph i n Figure 2.3 i l l u s t r a t e s some of the p o s s i b l e r e p r e s e n t a t i o n s as a sum of permutations. I 3 . 5 <* Figure 2.3 A 6-Point Cubic Graph I I : REPRESENTATIONS OF REGULAR GRAPHS 6 GENERATION METHODS 31 2.2 Representation as the Sum of Permutation Matrices U = •a. TT, Hi a. 3 \ G 2_ 4 -a 5" 5 Hr G I I 3 6 1 X 3 4- 5T G I \ TT, S" 3 G a 4 1 X i 1 4 3 G T^ 3 u 4- 2 S" I 3 , U = 1 a. 3 H c »* i 5" 3 4- IL G 1 ^ . i 3 TV3 G 4- 2. 1 3 One could u t i l i z e t h i s mode of re p r e s e n t a t i o n to co n s t r u c t r e g u l a r graphs of degree d by generating a l l dxn matrices U that s a t i s f y p r o p e r t i e s 1 to U of the Theorem. However, observe from the example that although a p a r t i c u l a r set of permutations corresponds to a unique r e g u l a r graph, a given r e g u l a r graph can be represented by many d i f f e r e n t s e t s of permutations. Four I I : REPRESENTATIONS OF REGULAR GRAPHS & GENERATION METHODS 32 2.2 Representation as the Sum of Permutation Matrices p o s s i b l e r e p r e s e n t a t i o n s of the given graph are demonstrated and there are more! C l e a r l y , t h i s method would y i e l d many isomorphic graphs and so f u r t h e r m o d i f i c a t i o n s are necessary. These r e s u l t s may be extended to reduce the t o t a l number of isomorphic graphs produced by r e s t r i c t i n g the c l a s s of r e g u l a r graphs to ones with even degree only. Suppose G i s a r e g u l a r graph of even degree d on n p o i n t s . Since a l l r e g u l a r graphs of even degree have a 2 - f a c t o r i z a t i o n , then G can be represented as the sum of d/2 permutations each of which i s a 2-factor of the graph. That i s to say, the c y c l e s of the permutations represent the undirected c y c l e s of the graph. i x c s \ 1 3 H 5 C 1 8 •S-ojcAt TI, a 3> H S" C 1 * • H,M-o|c\JU 3 4- 1 % i 1 S Q Figure 2.4 Representation of an 8-Point Graph Using the previous method, the graph i n Figure 2.4 would be represented by 4 permutations instead of 2. This r e f i n e d method of r e p r e s e n t a t i o n adds a d i r e c t i o n to the c y c l e s of the graph I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 33 2.2 Representation as the Sum of Permutation Matrices and so the re p r e s e n t a t i o n may be optimized f u r t h e r amongst graphs by imposing a d i r e c t i o n convention t h a t i f an s- c y c l e 1=x, #x i f ,x s #xs "S'-< occurs, then the reverse d i r e c t i o n c y c l e 1=x,,x s,x 5. x , ,x a,x,-1 i s not allowed. These ideas are formalized as f o l l o w s . Theorem 2.0 Let G be a r e g u l a r graph of even degree d on n p o i n t s . Let T I i * lTa.» '~^«tyx b e P e r n>utations that each represent a 2 - f a c t o r i n a 2 - f a c t o r i z a t i o n of G. Let the matrix U be defined by: 3 TT, TU JUL* s JU, then (1) nyx *i f o r j = 1 , 2 , — , a / 2 ; i = 1 , 2 , — , n (2) f o r a f i x e d i i n {1,2, ,n} u ^ ^ u ^ f o r j#k where 1<j,k<d/2 (3) the minimum length of any c y c l e of the permutations i s 3 (4) each member of the set {1,2,——,n) appears i n U e x a c t l y d/2 times I I : REPRESENTATIONS OF REGULAR GRAPHS 6 GENERATION METHODS 34 2.2 Representation as the Sum of Permutation Matrices Proof: (1) Suppose there e x i s t s j i n {1,2, rd/2} and i i n {1,2, ,n} such t h a t u ^ = i . This i m p l i e s that there i s a loop at node i of the graph which i s im p o s s i b l e . (2) Suppose f o r a f i x e d i i n {1,2, ,n} th a t u - = u k i = s where j#k and 1<j,k<d/2. This i m p l i e s that node i i s adjacent to node s i n two d i f f e r e n t 2 - f a c t o r s . C l e a r l y , t h i s i s a c o n t r a d i c t i o n . (3) This f o l l o w s d i r e c t l y from the f a c t that the minimum length of any c y c l e i n the graph i s 3. (4) Each member of the set {1,2, ,n} appears once i n each 2-f a c t o r . Since there are d/2 2 - f a c t o r s then each element i n {1,2, ,n} appears e x a c t l y d/2 times i n the matrix 0. This r e p r e s e n t a t i o n of a 2 - f a c t o r i z a t i o n of G i s a n x ^ l a t i n r e c t a n g l e . Thus i n order to generate r e g u l a r graphs of even degree d, we must generate a l l n x A l a t i n r e c t a n g l e s obeying r u l e s 1 t o 4 of the Theorem and f o l l o w i n g the d i r e c t i o n convention. Using the permutation generation algorithm by H e l l s [ 4 0 ] , a I I : REPRESENTATIONS OF REGULAR GRAPHS 5 GENERATION METHODS 35 2.2 Representation as the Sum of Permutation Matrices computer program was w r i t t e n to generate re g u l a r graphs using t h i s method of r e p r e s e n t a t i o n . However, the r e p e t i t i o n s were s t i l l q u i t e large due to the f a c t t h a t a r e g u l a r graph of even degree d may have s e v e r a l d i f f e r e n t 2 - f a c t o r i z a t i o n s . Figure 2.5 A Regular Graph of Even Degree The graph i n Figure 2.5 has the f o l l o w i n g 2 - f a c t o r i z a t i o n s : 8-cycle 8-cycle 1-2-3-4-5-6-7-8-1 1-6-2-5-7-4-8-3-1 4,4-cycle 8-cycle 1-6-7-8-1 2-3-4-5-2 1-2-6-5-7-4-8-3-1 3,5-cycle (1-3-8-1 2-5-4-7-6-2 8-cycle \l-2-3-4-8- 7-5-6-1 I f we f u r t h e r r e s t r i c t the graphs to be on an even number of p o i n t s with even degree d then we can u t i l i z e Baebler's r e s u l t that such a graph always has a f a c t o r of degree d/2. I I : REPRESENTATIONS OF REGULAR GRAPHS 8 GENERATION METHODS 36 2.2 Representation as the Sum of Permutation Matrices Thus a l l non-isomorphic r e g u l a r graphs of degree d/2 would be a b a s i s from which to b u i l d a l l the reg u l a r graphs of even degree d. However the number of r e p e t i t i o n s generated using t h i s method i s s t i l l q u i t e l a r g e , so we must look f o r something b e t t e r . 2.3 Canonical 2 - F a c t o r i z a t i o n I n order to f u r t h e r reduce the number of p o s s i b i l i t i e s , the 2 - f a c t o r s of r e g u l a r graphs were s t u d i e d i n hope of d i s c o v e r i n g a c a n o n i c a l 2 - f a c t o r i z a t i o n of re g u l a r graphs of even degree. Toward t h i s end the 2-factors of re g u l a r graphs on 8 points of degree 4 were examined. On 8 p o i n t s the p o s s i b l e 2 - f a c t o r s are: (i) an 8-cycle ( i i ) a 4-cycle and a 4-cycle ( i i i ) a 3-cycle and a 5-cycle Hence, the p o s s i b l e types of 2 - f a c t o r i z a t i o n s of a graph on 8 po i n t s of degree 4 are: (i) two 8-cycles ( i i ) an 8-cycle with a 3-cycle and a 5-cycle ( i i i ) an 8-cycle with two 4-cycles (iv) four 4-cycles (v) two 4-cycles with a 3-cycle and a 5-cycle (vi) two 3-cycles and two 5-cycles I I : REPRESENTATIONS OF REGULAR GRAPHS S GENERATION METHODS 37 2.3 Canonical 2 - F a c t o r i z a t i o n The p o s s i b l e 2 - f a c t o r i z a t i o n s of a l l the graphs on 8 points of degree 4 are shown i n Figure 2.6 ( a - f ) . U) 8-cyc le 1-2-3-4-5--6-7-8-1 8-cycle 1-4-7-2-5--8-3-6-1 ( i i ) 4, 4-cycle 1-2- 3-8-1 4-5-6-7 4 ,4-cycle i 1-4-3-6-1 a. 2-5-8-7 7 * ^ i 4 S U) 8-cycle 1-2-3-4-5- 6-7-8-1 4 ,4-cycle 1-4-8-5-1 2-6-3-7 -2 ( i i ) 4,4-cycle 1-2- 7-8-1 3-4-5-6 -3 4, 4-cycle 1-4-8-5-1 2-3-7-6 -2 ( i i i ) 8-cycle 1-5-8-4-3-7-6-2-1 8-cycle 1-4-5-6-3-2-7-8-1 : REPRESENTATIONS OF REGULAR GRAPHS & GENERATION METHODS 3 Canonical 2 - F a c t o r i z a t i o n I 3. (i) 8-cycle 1-2-3-4-5-6-7-8-1 3 ,5-cycle 1-5-7-1 2-4-6-3-8-2 ( i i ) 4,4-cycle 1-2-3-8-1 4-6-7-5-4 8- c y c l e 1-5-6-3-4-2-8-7-1 ( i i i ) 8-cycle 1-2-8-7-6-3-4-5-1 8-cycle 1-8-3-2-4-6-5-7-1 CO 1 1 . G S ( i ) 8-cycle 1-2-3-4-5-6-7-8-1 8-cycle 1-4-2-7-5-8-3-6-1 ( i i ) 3,5-cycle 2-3-4-2 1-6-5-7-8-1 8-cycle 1-2-7-6-3-8-5-4-1 ( i i i ) 4,4-cycle 1-4-5-8-1 2-3-6-7-2 8- c y c l e 1-2-4-3-8-7-5-6-1 oh I I : REPRESENTATIONS OF REGULAR GRAPHS 5 GENERATION METHODS 2.3 Canonical 2 - F a c t o r i z a t i o n I a. - g (i) 8-cycle 1-2-3-4-5-6-7-8-1 3 ,5-cycle 1-3-6-1 2-4-7-5-8- 2 ( i i ) 4, 4-cycle 1-3-2-8-1 4-5-6-7- 4 3, 5-cycle 1-2-4-3-6-1 8-5-7-8 ( i i i ) 8-cycle 1-2-4-7-8-5-6-3-1 8- c y c l e 1-6-7-5-4-3-2-8-1 C O Q S ( i ) 8- c y c l e 1-2-3-4- 5-6-7-8-1 4,4-cycle 1-5-3-6- 1 2-8-4-7-2 ( i i ) 8-cycle 1-2-7-6- 3-5-4-8-1 3,5- c y c l e 1-5-6-1 2-8-7-4-3- 2 ( i i i ) 8-cycle 1-5-6-7- 8-4-3-2-1 8-cycle 1-6-3-5-4-7-2-8-1 (iv) 3,5-cycle 1-2-8-1 3-5-4-7-6- 3 3, 5-cycle 1-5-6-1 2-3-4-8-7-2 Figure 2.6 2 - F a c t o r i z a t i o n s of 8-Point Graphs I I : REPRESENTATIONS OF REGULAR GRAPHS 5 GENERATION METHODS 40 2.3 Canonical 2 - F a c t o r i z a t i o n The only 2 - f a c t o r i z a t i o n which i s common to a l l these graphs i s the one c o n s i s t i n g of two 8-cycles. Unfortunately t h i s does not g e n e r a l i z e , s i n c e not a l l r e g u l a r graphs of even degree have a Hamiltonian c y c l e . However, according to a r e s u l t of Posa [17,p.66] a l l r e g u l a r graphs of degree d>n/2 have a Hamiltonian c y c l e . One can u t i l i z e t h i s f a c t i n the generation of r e g u l a r graphs of degree d>n/2; however, f u r t h e r r e s t r i c t i o n s are necessary to reduce the number of isomorphic graphs produced. As a consequence of t h i s observation, the generation algorithm i s r e s t r i c t e d to Hamiltonian cubic graphs. 2.4 A Dead-End I n v e s t i g a t i o n The purpose of t h i s s e c t i o n i s to e x p l a i n another p l a u s i b l e approach to the generation problem, and t o i n d i c a t e why t h i s method f a i l s t o y i e l d u s e f u l r e s u l t s . Suppose G i s a r e g u l a r graph of even degree d on n poi n t s . Let G, , G a, 'G4lx b e t h e 2 - f a c ' t o r s i n a 2-f a c t o r i z a t i o n of G. I f P i s the automorphism group of the graph G then S h the set of a l l permutations on n po i n t s can be decomposed i n t o cosets: s„/P = r + x , r + x , r + — - + x s p where x^£S r t. A r e p r e s e n t a t i v e permutation from each of the s cosets of the form x^ P would y i e l d a new graph when appli e d to G. However, computing the automorphism group p1 i s too complicated f o r such a method to be considered f e a s i b l e . I I : REPRESENTATIONS OF REGULAR GRAPHS 6 GENERATION METHODS 41 2.4 A Dead-End I n v e s t i g a t i o n Instead, i t might be p o s s i b l e to determine under what circumstances one can permute the nodes of a 2-fa c t o r to guarantee a new graph. The f a c t o r s of r e g u l a r graphs of degree 4 were examined i n an attempt t o analyse t h i s problem of how to generate a non-automorphism. The a n a l y s i s i n v o l v e s breaking down the problem i n t o s e v e r a l l e v e l s of cases. The simples t case i n v o l v e s c o n s i d e r i n g the e f f e c t of a permutation which i s a 2-cycle of the form (1 i ) . For each d i f f e r e n t type of 2 - f a c t o r , one must consider whether nodes 1 and i are connected, adjacent, or disconnected. For each of these sub-assumptions, other cases and sub-assumptions a r i s e concerning the nodes adjacent to each of 1 and i . Given the complete set of assumptions, one can e s t a b l i s h whether or not a new graph i s produced. However, the multitude of cases i n v o l v e d does not seem to y i e l d a general r e s u l t , and so one i s l e d to abandon t h i s approach. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 42 As mentioned i n Chapter I I , i t would be u s e f u l i n the generation process to u t i l i z e a 'canonical* f a c t o r i z a t i o n of a r e g u l a r graph. Inasmuch as no such f a c t o r i z a t i o n i s forthcoming, we s h a l l r e s t r i c t our a t t e n t i o n to Hamiltonian cubic graphs i n order to take advantage of the f a c t that a l l these graphs are the sum of an n-cycle and a 1-factor. A f o r m a l i z a t i o n of the algorithm i s presented a f t e r the i n t u i t i v e e xplanation of the main ideas. B a s i c a l l y the algorithm f o r generating Hamiltonian cubic graphs uses a notion of 'type' to construct ( l i n e by l i n e ) the 1-factor of the graph i n s i d e the n-c y c l e . S e v e r a l p o s s i b l e graphs are a u t o m a t i c a l l y e l i m i n a t e d due to symmetry. In a d d i t i o n t o t h i s , the p a r t i a l l y constructed graphs are p e r i o d i c a l l y examined f o r isomorphism using the n-c y c l e as a frame of reference. The algorithm i s not i d e a l i n that some graphs are produced more than once. The cubic graphs on 6, 8, 10, and 12 p o i n t s (to be presented l a t e r ) are evidence th a t the number of r e p e t i t i o n s i s a t an acceptable l e v e l . I n order to f u r t h e r c l a r i f y the a l g o r i t h m , the f o l l o w i n g d e f i n i t i o n s and n o t a t i o n are necessary. Let G be a l a b e l e d graph on n points {1,2, ,n} c o n t a i n i n g the b a s i c n-cycle 1-2-3-.. .-n-1. Let the maximum degree of each node of G be 3 and l e t node 1 be adjacent to node j where j#1,2,n. Let V,={i,=1,i x, (where s=2k) be the set of a l l nodes of G that are i n c i d e n t with a l i n e that i s not i n the I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 43 given n-cycle. Rename the elements of V, so t h a t i,=1<i i<i 3< < i s . Then the tvj>e of graph G i s an s-tuple ( t , , t a , , t s ) where t^ =1-^-1^ -1 f o r j = 1 , - — ,s-1 and t 4 = n - i s . The l e x i c o q r a p h i c tvjse of a graph G i s formed i n the f o l l o w i n g manner. Let ( t , , t a , , t 5 ) be the type of G. Rename the elements of the s-tuple so that t , < t ^ < — - ^ t s then the s-tup l e ( t , r t a , , t s ) i s the l e x i c o g r a p h i c type of G. Let x^ be a l i n e of G j o i n i n g nodes i r and i ^ where i r < i j • Then the gap leng t h of l i n e x^ i s equal to i y - i r - 1 . The algorithm manipulates l a b e l e d graphs with the bas i c n-cy c l e 1-2-3-...-n-1. I n i t i a l l y (n/2)-1 separate s t a r t i n g graphs are constructed. These are formed by s e t t i n g node 1 adjacent to each of nodes 3,4, ,2+((n/2)-1). For an 8-point graph the s t a r t i n g cases are shown i n Figure 3.1. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm For each s t a r t i n g case, a master matrix i s constructed to i n d i c a t e the p o s s i b l e adjacencies f o r the remaining nodes i n the graph. In a d d i t i o n to the obvious r e s t r i c t i o n s , i n the j + ^ s t a r t i n g case, no l i n e of gap length l e s s than j i s allowed since i t w i l l be included i n the previous cases. I t i s c l e a r that t h i s i n i t i a l approach e l i m i n a t e s many r e p e t i t i o n s even without an isomorphism a l g o r i t h m . Next, the algorithm processes one node at a time across a l l the cases to consider the p o s s i b l e adjacencies f o r t h i s node. For example, i n case ( i i ) of Figure 3.1 the p o s s i b l e adjacent nodes to node 2 are 5,6,7. Each of the p o s s i b l e l i n e s 25, 26, 27 are considered f o r a new intermediate graph i n the l i s t f o r case ( i i ) . However before the intermediate graph i s added, i t i s checked f o r isomorphism using the type isomorphism t e s t described below. A f t e r node 2 i s processed f o r each case, a type isomorphism t e s t i s a p p l i e d over a l l the intermediate graphs constructed over a l l the cases so f a r . The p o s s i b l e intermediate graphs f o r node 2 of the cases i n Figure 3.1 are given i n Figures 3.2, 3.3, and 3.4. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 45 Figure 3.2 Case (i) f o r 8-Points Observe that only graphs (a) , (b) , and (c) would be kept i n the l i s t of intermediate graphs f o r case (i) because (d) would be recognized as isomorphic t o (b), and (e) would be recognized as isomorphic to (a) . Figure 3.3 Case ( i i ) f o r 8-Points I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 46 A l l t hree of these graphs i n Figure 3.3 would be r e t a i n e d i n the l i s t of intermediate graphs f o r case ( i i ) . A f t e r c o n s t r u c t i o n of these graphs from node 2 a scan i s done over a l l three cases. In t h i s example there happens to be no r e p e t i t i o n among the l i s t of graphs f o r the d i f f e r e n t cases. The algorithm continues i n t h i s f a s h i o n processing nodes 3 through n-1. The type isomorphism t e s t used i n the algorithm r o t a t e s the graphs to match up p o i n t s on t h e i r r e s p e c t i v e b a s i c n-cycles i n an e f f o r t t o e s t a b l i s h an adjacency preserving mapping between them. For example, graph (i) i n Figure 3.5 would match with graph ( i i ) i n Figure 3.5 i f the nodes were ro t a t e d by the permutation ( 1 2 3 4 5 6 7 8 ) . 3 Figure 3.4 Case ( i i i ) f o r 8-Points X X Figure 3.5 Two Isomorphic 8-Point Graphs I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.0 I n t u i t i v e Explanation of the Algorithm 47 The type of the graph as defined i n t h i s Chapter becomes an i n v a l u a b l e a i d i n determining t h i s matching of the graphs. In order f o r two graphs t o match, a c y c l i c permutation of t h e i r types must match i d e n t i c a l l y . In Figure 3.5 the type of graph (i) i s (0,0,4,0) and the type of graph ( i i ) i s (0,0,0,4). In permuting the former graph to match the l a t t e r graph, i t s new type becomes (0,0,0,4) which matches i d e n t i c a l l y with the other type. Having the same l e x i c o g r a p h i c type turns out t o be a very u s e f u l necessary c o n d i t i o n f o r isomorphism. Ro t a t i o n of the graphs around the b a s i c n-cycle i s not always s u f f i c i e n t to match i d e n t i c a l graphs. Sometimes i t i s necessary to take the mirror image of a graph and then r o t a t e t h i s around the n-cycle. For example, graph (i) i n Figure 3.6 has type (0,0,3,1) and graph ( i i ) i n Figure 3.6 has type (0,1,3,0). I t i s c l e a r that these graphs are isomorphic, but r o t a t i o n around the n-cycle w i l l not match them properly. So a mirror image i s constructed from one of the graphs and t h i s w i l l c l e a r l y match with the other graph. In t h i s s i t u a t i o n both graphs must s t i l l have i d e n t i c a l l e x i c o g r a p h i c types i f they are indeed isomorphic. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 48 3.0 I n t u i t i v e Explanation of the Algorithm Figure 3.6 Two Isomorphic 8-Point Graphs This method of graph matching detects most of the isomorphic graphs. However, there are some graphs f o r which i t i s not s u c c e s s f u l . For example, consider the graphs i n Figure 3.7. l a . i -x i a . Figure 3.7 Three 8-Point Graphs Observe that graph ( i i i ) i s a r e w r i t t e n c o n f i g u r a t i o n of graph ( i i ) that would c l e a r l y match with graph ( i ) . The isomorphism here i s too s u b t l e to be detected by the graph matching process. Although t h i s matching process does not e l i m i n a t e a l l d u p l i c a t i o n s i n the generation algorithm, i t appears more p r a c t i c a l (at l e a s t f o r s m a l l values of n) to apply ad hoc methods to t e s t f o r isomorphism than to introduce a d d i t i o n a l transformations l i n k e d t o the b a s i c n-cycle. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.1 F o r m a l i z a t i o n of the Algorithm 49 The algorithm can be formalized as f o l l o w s where n i s the number of po i n t s i n the graph. Step 1. Label l i s t s L ( , L 1 # »L*-» t o b e u s e a t o keep a. t r a c k of graphs. Step 2. For each i , place i n l i s t L^ the graph c o n s i s t i n g of a basi c n-cycle 1-2-3-4-..,-n-1 plus the l i n e that connects node 1 and node 2+i. Step 3. Construct a - 1 master matrices M,,M^ , ,Mn corresponding to the graphs i n the l i s t s L;.. Each master matrix r e f l e c t s the remaining adjacencies allowed f o r each node i n case i . In a d d i t i o n , i n each master matrix M^ (for k=1, d i s a l l o w a l l l i n e s of gap length l e s s than k. Step 4. Set i=2. Step 5. Set m=1. Step 6. Set j=1. Step 7. R e t r i e v e graph G^  from l i s t L^. I f node i i n graph Gj i s of degree 3 then go to Step 16. I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.1 F o r m a l i z a t i o n of the Algorithm 50 Step 8. Let {n,,n a, #n^} be the set of p o s s i b l e adjacencies f o r node i according to master matrix M^. Step 9. Set k=1. Step 10. Produce graph G from graph G^, by adding a l i n e j o i n i n g nodes 1 and n to a copy of G- . Step 11. Let T, be the type of graph G and l e t T x be the l e x i c o g r a p h i c type of graph G. Step 12. Search the whole of l i s t L ^ f o r graphs of l e x i c o g r a p h i c type T a. For each graph of l e x i c o g r a p h i c type T» i n L w do matching t e s t s with graph G. I f no isomorphism i s found, repeat the matching with the mirror image of G. I f an isomorphism i s found, throw away graph G and go to Step 13. Otherwise add graph G t o l i s t L^. Step 13. Set k=k+1. Step 14. I f k<w go to Step 10. Step 15. Flag graph G •. to be deleted l a t e r from l i s t L . I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 51 3.1 F o r m a l i z a t i o n of the Algorithm Step 16. Set j=j+1. Step 17. I f there are more graphs i n l i s t L_ go to Step 7. Step 18. Delete a l l flagged graphs from l i s t L w . Set m=m+1. Step 19. I f m>§-1 go to Step 21. Step 20. Go t o Step 6. Step 21. Do a matching t e s t t o compare a l l graphs i n each l i s t of the same l e x i c o g r a p h i c type (include mirror image t e s t i f necessary). Delete any isomorphic graphs. Step 22. Set i=i+1. Step 23. I f i<n-1 go to Step 5. Step 24. Stop I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.2 Hamiltonian Cubic Graphs Generated 52 A computer program was w r i t t e n i n FORTRAN to implement the algorithm. (see Appendix I f o r a l i s t i n g of the program) . The r e s u l t s f o r 6, 8, 10, and 12 p o i n t s are given i n Table I. (see Appendix I I f o r a l i s t of the graphs). No. of Computer Graphs No. of D i s t i n c t P o i n t s Time Generated Rg£etitions Graphs 6 .95 sec. 2 0 2 8 1.08 sec. 7 2 5 10 8.25 sec. 29 11 18 12 744 sec. 188 109 79 TABLE I Results of Generation Algorithm I t appears l i k e l y from the computer times i n Table I that the computation grows e x p o n e n t i a l l y with the number of p o i n t s . The r e p e t i t i o n s were determined by computing the c h a r a c t e r i s t i c polynomials of the graphs, and by using ad hoc methods to t e s t f o r isomorphism among the graphs with the same c h a r a c t e r i s t i c polynomial. The number of r e p e t i t i o n s i s r e l a t i v e l y low and t h e r e i n l i e s the merit of the a l g o r i t h m . I l l : GENERATION 3.3 Order of the OF HAMILTONIAN Computation CUBIC GRAPHS 53 A loose upper bound on the number of graphs t o be processed a -i by the algorithm i s given by n"1 . Many of these cases are e i t h e r r e j e c t e d immediately or e l i m i n a t e d e a r l y i n the graph c o n s t r u c t i o n process, so t h a t , the number of graphs that are manipulated i s con s i d e r a b l y l e s s . However, the f a c t t h a t the e m p i r i c a l r e s u l t s r e v e a l an e x p o n e n t i a l l y growing computation time, suggests a strong c o n t r i b u t i o n from the graph matching process. The upper bound n * i s obtained i n the f o l l o w i n g manner. Let L, , L a , rl-a-i be the d i f f e r e n t s t a r t i n g cases. Node 2 can be adjacent to (n-3) nodes i n L,, (n-5) nodes i n L a , (n-7) nodes i n L,, ....... (n-[ ( s-1)*2 + 1 ]) nodes i n Lo., . A f t e r s a t i s f y i n g node 2, the next node has one l e s s p o s s i b l e adjacency. Proceeding i n t h i s f a s h i o n the r e s p e c t i v e numbers of p o s s i b i l i t i e s f o r the d i f f e r e n t cases are: T T ( u - ( i ^ ) ) 1 - t I t f o l l o w s t h a t the p o s s i b l e number of graphs i n each case Case (i) Case ( i i ) Case ( Q - 1 ) I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.3 Order of the Computation 54 i s approximately n ^  . Since there are ^.-1 cases, the upper Q -I bound over a l l cases i s n 1 . Out of the s i x cubic graphs on 8 p o i n t s , f i v e of them have a Hamiltonian c y c l e . R e c a l l t h a t I z b i c k i * s f i r s t method would count to 2 1 1 i n order to process binary matrices to generate the s i x graphs, and h i s algorithm would y i e l d many isomorphic graphs (in f a c t , no attempt i s made to reduce the r e p e t i t i o n s ) . Moreover, h i s second method would y i e l d a few hundred or more r e p e t i t i o n s . The above bound guarantees t h a t the algorithm presented i n t h i s Chapter processes a maximum of 2 graphs f o r the 8-point case. In f a c t only 17 graphs are processed by the algorithm and 7 graphs are produced with only 2 r e p e t i t i o n s . 3.4 Comments on the Computer Program The computer program was w r i t t e n i n FORTRAN making extensive use of code o p t i m i z a t i o n procedures so th a t the computation would be f e a s i b l e f o r s m a l l n. There i s a l a r g e amount of core reserved to s t o r e the intermediate graphs f o r each case. The main program uses 504098 bytes and t h i s would probably have to be expanded f o r n>14 (possibly f o r n=14 as w e l l ) . The program checks i t s e l f , and i f i n s u f f i c i e n t core i s a v a i l a b l e , i t gives an e r r o r message i n d i c a t i n g the problem. S e t t i n g the time l i m i t f o r t h i s program i s a problem, and I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3.4 Comments on the Computer Program 55 u n f o r t u n a t e l y , intermediate r e s u l t s are not very u s e f u l because the l i s t s of graphs c o l l a p s e as isomorphism checking i s done. The operating system could be of great a s s i s t a n c e i n t h i s s i t u a t i o n i f i t allowed one t o save a core image of the program that could be r e s t a r t e d where i t was l a s t i n t e r r u p t e d . In the program i t s e l f , graphs are s t o r e d i n l i s t s with t h e i r corresponding type, and l e x i c o g r a p h i c type. The graphs are represented i n storage as 1-factors s i n c e the outer n-cycle i s i m p l i c i t . For example, graph (i) i n Figure 3.7 would be sto r e d as the l i s t 3 7 1 6 8 4 2 5 which i s to be i n t e r p r e t e d as the edges 13, 27, 31, 46, 58, 64, 72, 85. The graphs are stored i n s e q u e n t i a l l i s t s f o r f a s t access and a 'hole f i n d i n g ' r o u t i n e p e r i o d i c a l l y detects and f i l l s holes i n the l i s t s . In a d d i t i o n , part of the program keeps t r a c k of the minimum and maximum length of the l i s t s of graphs f o r each case. For f u r t h e r d e t a i l s , see the program l i s t i n g i n Appendix I . 3.5 Conclusion Although the algorithm presented i n t h i s t h e s i s generates a large subset of cubic graphs, i t would be d e s i r a b l e to extend i t to generate a l l cubic graphs with no r e p e t i t i o n s . More g e n e r a l l y , one would l i k e to generate r e g u l a r graphs of any degree with no r e p e t i t i o n s . Since isomorphism determination I l l : GENERATION OF HAMILTONIAN CUBIC GRAPHS 3 . 5 Conclusion 56 dominates the computation time i n graph generation, a sound t h e o r e t i c a l framework i s needed to develop an algorithm which can recognize isomorphic r e g u l a r graphs i n polynomial time. I t i s c l e a r from the foregoing d i s c u s s i o n t h a t r e s t r i c t i n g the generation to reg u l a r graphs does not s i g n i f i c a n t l y reduce the complexity of the general problem. Perhaps the most promising t o o l f o r s o l v i n g graph isomorphism i s the concept of rook polynomials, or a s i m i l a r i l y defined s t r u c t u r a l polynomial which would d i s t i n g u i s h between isomorphic adjacency matrices. BIBLIOGRAPHY 57 1. BAEBLER, F. Uber die Zerlegung r e g u l a r e r Streckenkomplexe ungerader Ordnung. Comment. Hath. Helv. t 1_0 (1938), pp. 275-287. 2. BEATTY, J . C.; MILLER, R. . E. On Eg u i - C a r d i n a l R e s t r i c t i o n s of a Graph. Can.. Math_. B u l l A X 7 #3 (1964), pp. 369-375. 3. BENSON, Clark T. Minimal Regular Graphs of G i r t h s Eight and Twelve. Can t J j . H a t h j ^ 18 (1966) , pp. 109 1-1094. 4. BERGE, C. The Theory of Graphs,. Methuen 6 Co. L t d . London, 1964. 5., BROWN, W. . G. On the Non-Existence of a Type of Regular Graph of G i r t h 5. Can^ J.. Math t J L .19 (1967), pp. 644-648. 6. BOSACKER, H. G.; SAATY, T. L. F i n i t e Graphs and Networks^ McGraw-Hill Book Co., New York, 1965. 7. CHUARD, J . Graphes P l a n a i r e s homogenes de degre 3. J . of Comb. Theory, 1 (1966), pp. 411-436. 8. CORNEIL, D. G. Graph Isomorphism. Ph.D. Thesis, U n i v e r s i t y of Toronto, Dept. Of Computer Science, 1968. 9. CORNEIL, D. G. ; GOTLIEB, C. C. An E f f i c i e n t Algorithm f o r Graph Isomorphism. J.A.C.M., XI *1 (1970), pp. 51-64. 10. DJOKOVIC, D. On Regular Graphs I . Jj, of Comb. Theory^ 10 (1971), pp. 253-263. 11. FOLKMAN, J . Regular Line-Symmetric Graphs. of Cornb^ Theory^ 3 (1967), pp. 215-232. 12. FRUCHT, R. A One-Regular Graph of Degree Three. Caru Jj. Maika-x i (1952) , pp. . 240-247. 13. FRUCHT, R. Graphs of Degree Three with a Given A b s t r a c t Group. Caru J.. M a t h i X II (1949) , pp. 365-378. 14. GALLAI, T. On F a c t o r i s a t i o n of Graphs. Acta Mathematical Academiae Scientiarum Hungaricae t 1_ (1950), pp. ?33-1537 ~ 15. GILBERT, E. N. Enumeration of L a b e l l e d Graphs. £an. J t M a t h i x 8 (1956), pp. 405-411. 16. HALL, M.; KNUTH, D. E. Combinatorial A n a l y s i s and Computers. Amer.. Math. Monthly, 72 #2 (1965). 17. HARARY, F. Graph Theory^ Addison-Wesley, Reading, 1969. BIBLIOGRAPHY 58 18. HARARY, F. (ed.) Proof Techniques i n Graph Theory^ Academic Press Inc., Hew York, 1969. ~ 19. HEAP, B. R. The Production of Graphs by Computer. In Graph Theory and the Computer,, ed. by R. Read, Academic Press, New YorkT 1972. 20. HOFFMAN, A. J. On the Polynomial of a Graph. Amer.. Math. Monthly^ 70 (1963) , pp. 30-36. 21. IZBICKI, H. Regulare Graphen 3., 4., und 5. Grades mit vorgegebenen abstrakten Automorphismengruppen, Farbenzahlen und Zusammenhangen. Hpnatshefte f u r Mathematik x 61 (1957), pp. 42-50. 22. IZBICKI, H. Regulare Graphen b e l i e b i g e n Grades mit vorgegebenen Eigenschaften. Monatschefte f u r Mathematik, 64 (1960) , pp. ,15-21. 23. IZBICKI, H. Zur programmgesteuerten Erzeugung r e g u l a r e r Graphen. Monatshefte f u r Mathematik^ 70 (1966), pp. 337-346. 24. KAUTZ, W. H.; TURNER, J . (eds.) A Survey of Progress i n Graph Theory i n the Soviet Union. Supplement to Siam Review 1 2 (1970) . 25. KOTZIG, A. On Even Regular Graphs of the T h i r d Degree. Mat.-Fvjz. C as op i s Sloven. Akad. Vied.^ Vb (1966), pp. 72-______ 26. LEHMER, D.,H. The Machine Tools of Combinatorics. In Applied Combinatorial Mathematics ed. by E. F. Beckenbach, John Wiley and Sons, Inc., New~York, 1964. 27. LIU, C. L. I n t r o d u c t i o n to Combinatorial ____________ McGraw-Hill Book~Co., New~York, 1968? i 28. LOVASZ, L. On the S t r u c t u r e of F a c t o r i s a b l e Graphs. Acta Mathematica Academiae Scientiarum Hungaricae^ 23 (1972), pp7~179-195. 29. PETERSEN, J . Die Theorie der regularen Graphen. _____ _____x 1 _ (1891), pp. 193-120. 30. RADO, R. F a c t o r i z a t i o n of Even Graphs, fiuarterlj ________ (Oxford Series) 20 (1949) , pp. 95-104. 31. RAO, A. R. A C h a r a c t e r i z a t i o n of a Class of Regular Graphs. J.. of Comb. Theoryj. 1.0 (1971), pp. 264-274. BIBLIOGRAPHY 59 32. READ, R. C. Teaching Graph Theory to a Computer. In [39] p. 61. 33. RIORDAN, J. An I n t r o d u c t i o n t o Combinatorial A n a l y s i s ^ John Wiley S Sons~Inc7,~New~York,~1966.~ ~ 34. ROSEHFELD, M. Independent Sets i n Regular Graphs. I s r a e l J . Math., 2 (1964), pp. 262-272. 35. RYSER, H. J . Combinatorial Mathematics^ The Mathematical A s s o c i a t i o n of America, Rahway, 1963. 36. SAUER, N. On the Existence of Regular n-Graphs with Given G i r t h . J o u r n a l of Combinatorial T h e o r y 9 (1970), pp. 144-147. 37. SEIDEL, J . J . Strongly Regular Graphs. In [39] p. 185. 38. TUTTE, W. T. The Factors of Graphs. Can.. J.. Math. t 4 (1952), pp. 314-328. 39. TDTTE, W. T. (ed.) Recent Progress i n Combinatorics^ Academic Press, London, 1969. 40. WELLS, M. B. Elements of Combinatorial Computing t Pergamon Press, Hungary, 1971. 41. YAP, H. P. Some Ad d i t i o n Theorems of Group Theory with A p p l i c a t i o n s to Graph Theory. Can. J . Math. x 22 #6 (1970), pp. 1185-1195. MICHIGAN TERMINAL SYSTEM FORTRAN G (14 1 336) MAIN 01- 18-74 00:00:29 PAGE P001 OC01 0002 0003 0004 0C05 0006 0007 0008 0CO9 0010 001 1 0012 0013 0011 0015 0016 0017 00 18 0019 0020 0021 0022 002 3 002 4 C. C. C c c c c c c. i . ..PROGRAM TO GENERATE REGULAR' GRAPHS OF DEGREE 3 ON N POINTS l'STEGER*2 ADJCTX (160, 16),AEDF (16) ...ADJMTX IS A MASTER ADJACENCY MATRIX CONTAINING BANNED LINES ...ADCR IS THE ADDRESS MATRIX TO THE MASTER MATRIX IMTFGRR*2 GRAPH (10,500, 16) ,GTYPE (10,500,32) ....GRAPH (I,J,K) IS WHERE THE GRAPHS ARE 1C BE CONSTRUCTED, I IS THE CASE NUMBER, . . . . J IS THE EL ACE IN THE L I S T , K IS THE ADJACENCY FOR THE KTH POItiT; GIYPE (I, J,K) IS ....THE CORRESPONDING TYPES OP THE GRAPHS WHERE UNDER THE INDEX K, THE REAL TYPE FOLLOWED ...BY THE LEXICOGRAPHIC TYPE IS STORE! I tl T E G E R * 2 NGRAPH (10) ,NLINES (10,500),ENDLST (10),GARCOL(10, 100) , ISTA 1T (10) ....NGRAPH (J) IS THE CURRENT NUMBER CF PARTIALLY CONSTRUCTED GRAPHS IN THE JT.II CASE . ...NLINES (J,K) IS THE NUMBER OF LINES CONSTRUCTED IN THE KTH GRAPH OF TH E JTH CASE ...ENDLST (J) IS THE NEXT FREE WORD IN THE LIST FOR THE JTK CASE ....GARCCL (J.K) IS A MATRIX FOR GARBAGE COLLECTION OF THE LIST OF GRAPHS ...1STAT(J) CONTAINS MAX NO GRAPHS CONSIDERED FOR CASE J I N T E G E R * 2 T Y P ( 3 2 ) , T Y P 1 ( 3 2 ) , P A E J ( 1 6 ) , P P T S ( 1 6 ) , P P T S 1 |16),PADJ1 (16),E 1FLIP (100) ,FLADDR (16) C . ...TYP (J) ,?YP1 (K) ARE TEMPORARY STORAGE AREAS FOR MANIPUIATING TYPES C OF GRAPHS C . ...PACJ (J) .EFTS (K) ,PPTS1 (L) ARE TEMPORARY STORAGE AREAS FCB POINT C ADJACENCIES INTEGER*2PTER1,PTER2 INTEGER CCNS1,CONS2,CONS3,CONS4,CONS5,CONS6,CONS7,CONS8,CONS9 RESERVE LAEELLED COMMON AREAS -COMMON /NUMPT/ NPTS CCCrCN / L I S T I S / PADJ,PADJ1,CONS1,TYP,TYP1,PPTS1,PPTS . . . I N I T I A L I Z E STORAGE AREAS E AT A GRAFI-:/R0000*0/ . DATA GTYPE/16CC00*0/ DATA NG R A E H/ 10*0/ DATA NLINES/5000*0/ C AT A F.NCLST/10*1/ DATA GARCOL/1000*0/ IATA ISTAT/10*0/ DATA PFLIP/2,1,4,3,2,1,6,5 ,4,3,2, 1,8,7,6,5,4,3,2,1,10,9,8,7,6 ,5,4, 13,2,1,12,11,10,9,8,7,6 , 5,4.3,2, 1,14, 13,12,11,10,9,8,7,6 , 5,4 , 3,2,1, 116,15,1(1,13,12,11,10,9,8,7,6,5,4,3/ DATA F L A t t R / 0 , 0 , 0 , 0 , 0 , 4 , 0 , 1 0 , 0 , 1 8 , 0 , 28 , 0,40 , 0,54/ ....READ NUMBER OF POINTS NPTS, AND CONSIDER POSSIBLE NUMBER OF ADJACENCIES FCR THE POINT 1 01 THE GRA PRINT 1 FCRMATC TYPE IN THE NUMBER OF POINTS <17 IN 12 FORMAT •) READ (5,2) NPTS FC PC AT (12) IF ( (2* (NPTS/2)).EQiNPTS)GO TO 3 FBI NT 4 4 FORMAT (• ER ROB, THE NUMBER OF POINTS IN A CUBIC GRAPH BUST BE EVEN 1 , TRY AGAIN') C. 1.000 2.000 3.COO 4.000 0^ 5.COO 6.000 —i O 6.OCO M 7.000 X 7.000 H 8.000 8.CCO H3 9.000 ST 10.000 <D 10.000 Co 11.000 Co 1 1.000 3 12.000 T) 0 12.000 13.000 CD 14.000 a 14.COO 15.000 "0 16.000 o 16.000 on 17.000 17.000 fcl 18.000 C3 18.CC0 19.000 20.000 21.000 22.000 23.000 24.000 25.000 26.000 27.000 28.COO 29.000 30.000 31.000 32.COO 33.000 34.CCO 35.000 38.COO 38.000 39.COO 40.000 41.COO 42.000 6> 43.000 O 44.000 45.000 45.000 MICHIGAN TERMINAL SYSTEM FORTRAN G (41336) MAIN 0 4 - 18-74 0 0 : 0 0 : 2 9 PACE P002 0025 0026 0027 0028 0029 0030 003 1 0 03 2 0033 0 0-3 4 0035 0036 0037 0038 0 0 3 9 0 04C 004 1 0042 OOU 3 oouu 0045 004b 0047 0048 0049 0050 005 1 0 05 2 0 05 3 0054 0055 0 05 6 0057 0058 0059 0060 0 061 0062 0C63 0064 0065 0066 0067 0068 0069 0070 GC TC 5 C. . ..CALCULATE THE 3 OF CASES TO BE CONSIDERED FOR NODE 1 OF THE GRAPH 6 C... c. OF CASES BY BANNING LINES OF THAT TYPE IN NO. CCNS1=NPTS/2-1 •SETUP ADDRESS MATRIX TO THE MASTER MATRIX 1=1 IC 6 J=1,NPTS ACDR(J)=I I=I*CCNS1 .SETUP MASTER MATRIX FOR EACH CASE .COEI5 0=VACANT 1=AEJACENT - 1=PERMANENTLY UNAVAILABLE DO 10 J= 1 ,CONS1 EO 11 K=1,NPTS IX=ACDH (K)+J-1 IY=0 IF (K.EQ. 1)IY=-1 IF (K.EQ. (J + 2)) IY=-1 DO 12 L=1,NPTS 12 AEJMTX ( IX,L)=IY IF ( IY .N5.0) ADJMTX (IX, 1) = 1 ADJMTX ( IX , J + 2)=- 1 IJ=K+1 IF (K.EC.NPTS) IJ=1 ADJMTX ( IX , I J ) = 1 11 ACJCTX ( IX ,K)= -1 AUJKTX ( J , J + 2) = 1 10 CONTINUE C . . . .PREVENT OVERLAP C SUCCESSIVE CASES DO 20 J=2,CONS1 EO 21 K=2,NPTS IK1=K+J IF (IK1.GT.HPTS) 1K1=IK1-NPTS IK2=K-J IF (IK 2 .LT . 1) 1K2=IK2-»NPTS IX=ACDH(K) EO 22 KK=J,CONS1 IY=IX+KK-1 IF (ACJMTX ( IY, IK1) 22 IF (ADJMTX ( IY. IK2) 21 CONTINUE SO CONTINUE C . . . . SET-UP THE POSSIBILITIES FOR NODE 2 PPTS(1) = 1 PFTS(2) = 2 I DO 30 J=1,CONS1 I=AEER (2)-1+J PPTS (3)=J + 2 PACJ(1)=J*2 PADJ(J+2) -1 EO 3 1 K=4,NPTS C . . . . F I N D A POSSIBLE ADJACENCY FOR NODE 2 IF (A EJMTX ( I , K ) . N E. 0)GO TO 31 IF (K.EQ. (J+2))GO TO 31 C . . . .CCKPUTE TYPE OF GRAPH PADJ(2)=K . NE. 1)AEJMTX ( IY . IK1)=-1 .NE.1)ADJMTX(IY, IK2)=-1 46.COO 48.000 49 .000 APPE 52.000 APPE 53.000 APPE 54.000 55.000 t) 56.000 H X 59.000 60.000 61.COO 62.000 Dhe 63.000 Dhe 64.000 65.000 Comp 66.000 Comp 67.000 Comp 68.000 69.000 c+ 70.000 CD 71.000 72.000 T) 73.000 74.000 o oq 75.000 >-i 76.000 79.000 3 79.000 80.000 81.000 82.000 83.000 84.0CO 85.000 86.000 87.000 , ee.oco •' 89.000 90.000 9 1.000 92.CCO 95.000 96.000 97.000 98.000 99.000 100.000 101.000 102.COO 103.000 104.COO O l 1 105.000 106.000 107.000 108.000 MICHIGAN TERMINAL SYSTEM FORTBAN G (4 1336) MAIN 0 4 - 1 8 - 7 4 0 0 : 0 0 : 29 PAGE P003 007 1 PADJ (K) = 2 109.000 0072 FPTS (4) = K 110.0C0 0073 CALL SORT (PPTS,3,4) 11 1.000 Tf 0074 NLIN=2 112.000 Tl 0075 CALL GTYP (PPTS,NLIN,TYP) 113.000 0076 CALL LISOM (NLIN,J, ISOM,FLADDR,PFLIP,GRAPH ,GTYPE,ENDLST,NLINES,NGRA 114.000 O H Jxj 1PH) 114.000 0 07 7; IF (ISOM.EQ.1)GO TO 32 115.000 C . ACC GRAPH TO LIST 116.000 0078 I Y = ENDLST (J) 117.000 t-H 0079 IX=FADJ (1) 118.000 OOHO IAX=PADJ(2) 119.000 008 1 GRAPH ( J , I Y , 1) = IX 120.000 CD 0 08 2 GRAPH ( J , I Y , I X ) = 1 121.COO o o 0 08 3 GRAPH (J , IY ,2)=IAX 122.000 0084 GRAPH (J , IY , IAX)-2 123.000 3 0085 IZ=4*NLIN 124.000 0086 DO 3 3 L=1,IZ 125.000 £ 0 08 7 GTYPE ( J , I Y , L ) = TYP(L) 126.000 c+ CD •I 0088 33 CONTINUE 127.000 0089 NGRAEH (J)=NGRAPK (J)•1 128.000 T) 0 09 0 NLINES(J , IY)=NLINES(J , IY)+2 129.000 0091 ENCLST (J)=ENCLST(J)•1 130.000 T 0 09 2 ISTAT (J)=ISTAT (J)+1 131.COO 0 09 3 IF (ENCLST (J) .EQ.50 1)GO TO 1000 132.000 C . . . . Z E R O WORKING VALUES, 133.000 fu 3 0094 . 32 PACJ (K)=0 134.000 0095 PADJ (2) - 0 135.COO 0096 PPTS (4)=0 136.000 0097 31 CONTINUE 137.COO 0 09 8 FPTS (3) =0 138.000 0099 PADJ (1) =0 139.000 0 100 PACJ (J + 2)=0 140.000 0 10 1 30 CONTINUE 141.000 C . . . . C C AN ISOMORPHISM SCAN OVER ALL CASES FOR NODE 2 144.000 0 102 CALL CASISO (FLADDR,PFLIP,GRAPH,GTYPE, ENDLST,NLIHES,NGRAPH) 145.COO 0 103 PRINT 1004, (ENCLST (IKX) ,IKX=1,CONS 1) 146.000 0 104 1004 FORMAT (* ' , 10(13,2X)) C . . . G A R B A G E COLLECTION OF LIST OF GRAPHS 147.000 150.000 0 105 DO 2000 IKX= 1.C0NS 1 151.000 0 106 IKW=ENCLSt ( IKX) -1 152.000 0107 IF (IKW.EC.O)GO TO 2000 153.000 0 10U GARCOL (IKX,1)=0 154.000 0 109 IKY=2 155.000 0 110 DO 2001 IKZ=1,IKH 156.000 0 111 IF (GRAPH ( IKX , IKZ , 1) .N E.0)GO TO 2001 157.000 0 112 GARCOL (IKX, 1)=GARCOL (IKX, 1)+1 158.000 0113 GARCOL (IKX,IKY)=IKZ 159.000 0 114 IKY=tKY*1 160.000 0 115 IF ( IKY.EQ. 100)GO TO 2000 161.000 0 116 2001 CONTINUE 162.000 o 0117 2000 CONTINUE 163.000 C . . . P R O C E S S NODES 3 THRU (NPTS-1) 165.000 0118 IE=NPTS-2 166.000 0119 DO MO IT=3,IE 167.000 MICHIGAN TERMINAL SYSTEM FORT F A N G (41-136) MAIN 0 4 - 18-74 0 0 : 0 0 : 2 9 PACE P004 0 120 CONS2=IT-1 168.000 0 12 1 CCK34=IT+1 169.000 > C . . . .PRCCESS F A CH CASE 170.000 0 122 DO 41 J=1,CONS1 171.000 0123 I A C= A E CR ( IT) -1+J 172.000 0 124 IEN = EHDLST ( J ) - 1 173.000 a 0125 IF (IEN.EO.O)GO TO 4 1 174.000 M X C . . . .SEARCH LIST FOR VALID GRAPHS TO PROCESS 175.000 0126 CO 42 K=1,IEN 176.000 M 0 127 IF ( (GRAPH ( J .K ,1 ) .EQ.O) .OR. (GRAPH ( J ,K , IT ) .NE.O) )GO TO 42 177.000 0 128 NLIH = NLINES (J,K) +1 178.000 0 129 CONS3=4*NLIN 179.000 & CD C « * • .COMPUTE AEJACENCIES 180.000 0 130 DO 46 LL=1,NPTS 181.COO o 0131 IY=GRAPH(J.K.LL) 182.000 o 0 132 IF ( IY .EQ.0)GO TO 46 183.000 3 ct 0 133 PAEJ(LL)=IY 184.000 0 134 PADJ(IY)=LL 185.000 0 135 46 CONTINUE 186.000 CD C. . . .SEARCH FOR POSSIBLE ADJACENCY TO THIS NCDE 187.OCO 0 136 DO 45 L=CONS4,NPTS 188.000 T) >~i 0 13 7 IF (ADJMTX ( IAD,L) .NE.0)GC TO 45 189.000 C m • • .CHICK TO SEE IF NODE L IS ALREADY IN USE 190.000 O 0 13 8 DO 43 LL=1,CONS2 191.000 3 0 13 9 IF (GRAPH ( J , K , L L ) . N | . L ) G O TO 43 192.000 0 140 GOTO 45 193.000 0 14 1 4 3 CONTINUE 194.000 0 142 PADJ (IT)=L 195.000 0 14 3 PADJ(L)=IT 196.000 0 144 IX=1 197.COO 014 5 CO 47 LL=1,NPTS 198.000 0 146 IF (PADJ (LL).EQ.O)GC TO 47 199.OCO 0147 PPTS(IX)=LL 200.000 0 148 IX=IX+1 201.COO 0149 47 CONTINUE 202.000 0 150 CALL GTYP (PPTS,NLIN,TYF) 204.000 0151 CAIL LIS CM ( N U N , J, ISCM,TLADCR,PFL1P,GRAPH,GTYPE,ENDLST,NLINES,NGRA 1PH) 205.000 205.000 0152 IF (ISOM.IQ.1)GO TO 52 206.000 • C . . .ADD GRAPH TO LIST 207.000 C • • • •CHECK IF IT IS A VALIC GRAPH 208.000 0 153 IF ( (NLIN.EQ. (NPTS/2- 1)) .AND. (TYP (CONS3).EQ.2))GO TO 52 209.000 0154 IF (GRAPH (J .K, IT ) .EQ.O)GO TO 50 210.000 C • • • .ADD GRAPH AT END OF LIST 211 . 0 0 0 0155 . IX=ENELST(J) 212 . 0 0 0 0 156 IKX=GARCOL (J ,1) | 213.000 0157 IF(IKX.GE.I)IX=GARCOL ( J , IKX*1) 214.000 0158 DO 48 LL=1,NPTS 215.000 0159 48 GRAPH ( J , I X , L L ) - P A D J (LL) 216 .000 0160 NLINES (J,IX)=NLIN . ' ' 217 .000 0161 CO 49 LL=1,CONS3 218 .000 O N 0 162 49 GTYPE (J , IX ,LL)=TYP(LL) 219.000 0163 IF ( IKX.GE.1)GO TO 2002 220 . 0 0 0 0164 ENDLST (J)=ENDLST (J) + 1 2 2 1 . 0 0 0 0165 IF (ENCIST ( J ) . E Q . 5 0 1)GO TO 1000 222,000 MICHIGAN TERMINAL SYSTEM FORTRAN G (4 1336) MAIN 0 4 - 18-74 0 0 : 0 0 : 2 9 PAGE P005 0 166 'i GO TO 2003' - 223.000 0 167 2002 GARCOL ( J , 1) =GARCCL ( J , 1 ) -1 224.000 0168 2003 NGRAPH (J)-NGRAPH (J) +1 225.000 0 169 ISTAT (J) =ISTAT (J) + 1 226.000 0 170 GO TO 52 227.000 0 17.1 50 GRAPH(J.K,IT)=L 228.000 0 172 GRAPH (J ,K,L)=IT 229.000 0 17 3 NLINES (J,K)=NLIN 230.000 0 174 DO 51 LL=1,CONS3 231.000 017 5 51 GTYPE ( J ,K ,LL )= TYP (LL) 232.000 0 176 52 PADJ(IT)=0 233.COO 0 177 PACJ(L)=0 234.000 0 178 DO 5 3 LL=1,CONS3 235.000 0 179 53 TYP (LL) =0 236.000 0 180 DO 54 LL=1,NPTS 237.000 0 18 1 54 PPTS(LL)=0 238.000 0 182 45 CONTINUE 239.000 0 183 CO 55 LL=1,NPTS 240.000 0 184 55 PADJ(LL)=0 24 1 .COO 01,8 5 42 CONTINUE 242.000 0 186 4 1 CONTINUE 243.000 C . . . . CO AN ISCMCRPH1SM SCAN OVER ALL CASES FOR THIS NODE 244.000 0 187 CALL CAS I SO (FLADDH.PFLI P. GRAPH, GTYPE, ENDLST, NLINES, NGR API!) 245.000 018 8 PRINT 1004, (ENDLST (IKX),IKX=1,CONS1) 246.000 c. . . . GARBAGE COLLECT THE LIST OF GRAPHS 248.000 0 189 CO 2004 IKX=1,CONS1 249.000 0 190 IKW = ENDLST ( IKX) - 1 250.000 019 1 IF (IKW.EQ.O)GO TO 2004 251.000 0 19 2 GARCOL (IKX, 1)=0 252.000 0 193 IKY = 2 253.000 0194 CO 2005 IKZ=1,IKW 254.000 0 195 IF (GRAPH ( IKX , IKZ ,1 ) ,NE .0 )GO TO 2005 255.000 0196 GARCOL (IKX, 1)=GARCOL (IKX,1)+1 256.000 0 197 GARCOL (IKX,IKY)=IKZ 257.000 0198 IKY=IKY41 258.000 0 19 9 IF ( IKY.EQ. 100)GO TO 2004 259.COO 0200 2005 CONTINUE 260.000 020 1 2004 CONTINUE 261.000 0202 40 CONTINUE 264.000 C ..OUTPUT GRAPHS 266.000 0203 IX=NPTS/2 267.000 0 20 4 IV = 0 268.000 0205 CO 60 J=1,CONS1 269.000 0206 IY=ENDLST(J) 270.000 0207 DC 61 1=1,IY 271.000 0208 IF ( (GRAPH (J,I, 1).EQiO).OR. (NLINES(J,I) .LT.IX) )GO TO 61 272.000 0209 WRITE (7,62) (GRAPH (J,I,L),1=1,NPTS) 273.000 0210 62 FORMAT(16I2) 274.COO 021 1 I V = I V » 1 275.000 0212 61 CONTINUE 276.000 0213 60 CONTINUE 277.000 0214 WRITE (6 ,63) IV,NPTS 278.000 0215 63 FCRBAT (13,12) 279.000 0216 DO 64 1=1, I V 280.000 0 2 1 7 BEAD (8,62) ( PACJ {J),J= 1,NPTS) 281.000 > S3 a H x i-3 CD O O 3 c+ CD - 0 o era &3 B MICHIGAN TERMINAL SYSTEM FORTRAN G (41336) MAIN 04- 18-74 0218 WRITE (6,62) (P A C J (J),J=1,NPTS) -0219 64 CONTINUE C . . .. PRINTOUT THE S T A T I S I T I C S 0220 PRINT 65 022 1 65 FORMAT ( 1H 1,'MAX',4X, • MIN") 0222 DO 66 1=1,CONS 1 0223 PRINT 67,ISTAT (I) ,NGRAPH (I) 0224 67 FORMAT (1H ,I5,2X,I5) 0225 66 CONTINUE 0226 STOP C • • • • ERROR CONDITION NOT ENOUGH CORE 0227 1000 PRINT 1001 0228 1001 FORMAT (' ERROR NOT ENOUGH CORE ASSIGNED *) 0229 PRINT 100 2,IT, (ENCLST (J) , J = 1,CONS1) 0 23 0 1002 FORMAT (' NODE=',I2,2X, 10 (13,2X)) 0 23 1 STOP 0 23 2 END •OPTIONS IN EFPECT* IC,EEC CIC,SOURCE,NCL1ST,NODECK,LOAC,NOMAP •OPTIONS IN EFFECT* NAME - MAIN , LINECNT = 57 •STATISTICS* SOURCE STATEMENTS = 232,PROGRAM SIZE = 504098 •STATISTICS* NO CIAGNOSTICS GIN ER AT E C 00: 29 PAGE P006 282.000 283.000 284.COO 285.000 286.000 287.000 288.000 289.000 290.COO 291.000 292.000 293.000 294.000 295.000 296.000 297.000 298.000 13 w H Ix! f-H r-3 tr CD o o 3 C c+ CD *1 T) -i O 0*3 4 P 3 MICHIGAN TERMINAL SYSTEM FORTRAN G (41336) GTYP 04- 18-74 00:01:23 PAGE P001 0C0 1 StlEROtlTINB GTYP (ADJ,NLIN,TYP) 299.000 C . ..COKPUTING TYPE ANE LEXICOGRAPHIC TYPE OF A GRAPH 300.000 0002 I N T E G E R S ADJ (16) ,TYP (32) 301.000 0003 CCKKCN /NUMPT/ NPTS 302.000 0004 IX=2*NLIN 303.000 0C0 5 IJX=2*IX 304.000 0006 DO 1 J=2,IX 305.COO 0007 JJ=J-1 306.000 0006' TYP (JJ)=ADJ (J)-ADJ ( J J ) - 1 307.000 0009 1 TYP (JJ+IX)=TYP(JJ) 308.000 0010 TYP (IX)=NETS-ACJ (IX) 309.000 001 1 TYP (IIX)=TYP(IX) 310.COO 0012 IX=IX+1 311.000 C....FIND LEXICOGRAPHIC TYPE 312.000 0013 CAIL SORT (TYP,IX,IIX) 313.000 0014 RETURN 314.000 0015 ENE 315.000 • OPTIONS IN EFFECT* ID,EBCDIC,SOURCE,NOLI ST,NODECK,LOAD,NOMAP •OPTIONS IN EFFECT* NAME = GTYP , LINECNT = 57 •STATISTICS* SOURCE STATEMENTS = 15,PROGRAM SIZE = •STATISTICS* NO EIAGNOSTICS GENERATE! 602 T) ft O . M X H i-3 CD o o 3 c+ CD T J o 4 3 O N MICHIGAN 000 1 0002 0 00 3 0004 0005 0006 0C07 0008 0009 0010 001 1 0012 00 1 3 0 0 10 0015 0016 0017 0018 0019 0020 002 1 0022 0023 0024 0025 002G 0027 0028 0029 0030 003 1 0032 003 3 003« 0035 003 6 0037 0038 0039 0040 0041 TERMINAL SYSTEM FORTRAN G (41336) LISOM 04-18-74 00:01:24 PAGE P001 C . C C . C . C . C . 30 ADC IT 3 C . C . 6 C . 22 C . 11 c. SUBROUTINE LISOM (NLIN,ICASE,ISOM,FLACDR,PFLIP,GRAPH,GTYPE,EMDLST,N 1LINES.NGRAPH) ...ISC CHECK IN LIST, ISCM=0 MEANS ALE TC LIST, ISOM=1 KEANS THERE IS ALREADY SUCH A GRAPH INTEGER CCNS1 INTEGER*2 TYP1 (32),PPTS1 (16) ,PPTS (16) .GRAPH (10,500, 16),GTYPE(10, 50 10,32) ,ENELST (10),NLINES(10,500) INTEG ER *2 P A D J 1 (16),PADJ (16) ,TYP (32),PFLIP (100),FLADDR (16),NGRAPH ( 110) COMMON /LISTIS/ PADJ,PADJ1,CONS1,TYP,TYP1,PP1S1,FPTS CCfKCN /NUMPT/ NPTS KK = ENDLST (ICASE) IfLAG2=0 ISCK=0 IF (KK. EQ. 1) RETURN ..FIRST GRAFF IN THE LIST DO 2 J=1,KK ..FINE A VAL1C GRAPH IF (GRAPH (ICASE,J,1).EQ.O)GO TO 2 ..CHECK THAT THE NUMBER CF LINES IS THE SAME IF (NLIN.NE.NLINES (ICASE,J))GO TO 2 : ..COMPARE LEXICOGRAPHIC TYPE IX = 0 L K = 2* NLIN L=LK+1 II=4*NLIN DO 3 I=L.LL IF (TYP (I),EQ.GTYPE (ICASE,J,I))GO TO 3 GOTO 2 CONTINUE ..COMPARE FORWARD CYCLES IN REAL TYPE ..SET-UP TYPE ANE ADJACENCIES FOR GRAPH IN LIST DO 5 1=1,LK TYP1 (I)=GTYPE (ICASE,J,I) IY=1 CO 6 1=1,NPTS IF (GRAPH (ICASE,J,I).EQ.OJGO TO 6 PPTS1(IY)=I TY=IY» 1 CONTINUE >.PERMUTE FORWARD AND COMPARE TYPES IF1AG1=0 DO 10 1=1,LK ..COKPARE TYEES DO 11 K=1,LK IE (TYP (K).EQ.GTYPE (ICASE,J,K))GO TO 11 GO TO 13 CONTINUE .CHECK FOR ISOMORPHISM IFt A G=0 DO 14 K=1,LK IX = PPTS.(K) IY = PADJ (IX) IAX=PPTS1 (K) IAY=GHAPH (ICASE,«J,IAX) 316.COO 316.000 . > 317.000 • Tl Ti H 3 17.COO 318.000 S 3 19.000 319.COO H X 320.000 320.000 N 321.000 322.COO 323.000 CD 324.000 325.000 O 326.000 O 3 -d 327.000 328.COO 329.000 ct 330.000 CD 331.000 332.COO TJ 333.000 334.C00 O 335.000 33 6. COO 337.000 3 338.000 339.000 340.000 34 1.000 342.000 343.000 344.COO 345.000 346.000 347.000, 348.COO 349.000 350.COO 351.000 352.000 353.000 354.000 355.000 356.000 357.000 358.000 359.000 360.COO 361.000 ON 362.000 363.000 364.000 365.000 366.000 o o o o o o o o o o o o o o o o o o o o o o o o ° o o o a o o o o o o o o o o o o o o o o o o o vo 43 vo >a so co m tn oo co co ro oo co oo »j ^ ^ 2 S 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 ° o o o o o o o o o o o o n °, S 2 ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° o o o o o o o o o 5 o 2 M - O H H s» -a x > x rt H O II Ul T3 Cj K —« >n —» » — rt-« X M U 1 H + 3» - . X W II II > M tJ X X f M M M 1-4 O > x x ra x o n i l II — ii C j T3 T3 M tn ro —» ra »n x to —» — f f • » • H H I I-H ra T3 7i X U T l O 3 II • Ml II II U -» f o o H H H » M II 3 » II H X O H < t-i x + w n z x + H n » >3 tr"-' r u m — rt » o o rt r3 X TI TJ 1-3 -» C/l • l-l '7, K n o z f n rt 1 "0 rt O < c : n x T l O — i — i » ra ra 3C Z X) rt ui — k — ' rt 7) K J II H I — -> o —" i *» CJ »• X HI z p ; -—- z a X c: — ! X PC o er> m II ~ 11 rt rt II _» rt o n X T3 « S3 o T) H X GC rt f UJ T J S» 3» —* Q a> . > rrf » M Z rt X — V w C/J c i M 3 " t-c rt => rt o O I-I H I t-i ro ro H I H I f x X KJ II VI ra ii II ii r; u - . n -r* rt "3 x II *Tl - » t - c> c i > o o ci z • rt rt ra n o © z • c - i -* m o o o • rt o M ^ M H 3» r-l C l t --» ra o h-t rt H I HI h-i H I H I HI M HI •-I HI t—> H I X- »• a - ra r c f II rn e- X X ! Ii ~ . li II t-H M II II II II H I rt i-« HI H I H I z H I H I i-l » S" l - i rt £-* t - > S» X X f — • rt X X • t - 1 Cl ra 1 H I rt • M > « M S» X HI HI 1 S" 1 > X — " . Cl +• Cl o l-( o 3> rt X rt o o _ —A . 00 il II s* ra li — - II II X X ! il II Z H I H< H J M f C - T3 X • rt I f W w ra i x • M I HI X _» "—' — i o + O HI X rt o rt o to rt 5= M rt ra ra Z .—. .—» H I H I o x ra . . • r-rt Cl • _» UJ M • x ra -—• — o Cl • o - « ' - 1 HI O s> X -> li U l t ) x> a o —. t-" w B< in X a ~— c I I ^ o - j 3 r o - ^ ^ u i c u . K j ^ o o r o ^ m u i c - u j K j ^ o ^ r o ^ S u i £ S ^ S S ^ ^ S ^ m r o m m | | | | § g § § § g g g g g g g g g g § g g § g g g g g g g o o o o o o o ^ o o o o o o o o o o o o o o o o o o o o o o g g g g g g g g g g g g g g g g g g g g g g g g g g o o o o o o o 13 s» m o o KJ $9 MICHIGAN TERMINAL SYSTEM FORTRAN G(41336) LISOM 04- 18-74 00:01:24 PAGE P003 0095 21 CONTINUE 422.000 0096 CALL SORT (PPTS1,1,LK) U23.000 0097 CALL GTYP (PFTS1,NLIN,TYP1) U2<4.000 0098 GO TO 22 1425.000 C . . .ZERO WORKING MATRICES 1426. 000 0099 23 DO 24 K=1,LK 1427.000 0 100 PPTS 1 (K) =0 1428.000 0101 TYF1 (K)=0 1429.000 0 102 TYP1 (K + LK)=0 430.000 0 10 3 24 CONTINUE 43 1.000 0 104 IF (IFLAG2.EQ.1)RETURN 432.000 0.105 2 CONTINUE 433.000 0 106 RETURN 434.000 0 107 ENE 435.000 •OPTIONS IN EFFECT* ID,EBCDIC,SOURCE , NOLI ST,NODECK,LOAD,NOMAP •OPTIONS IN EFFECT* NAME = LISOM , LINECNT = 57 •STATISTICS* SOURCE STATEMENTS = 107,PROGRAM SIZE = •STATISTICS* NO DIAGNOSTICS GENERATEC 2476 tS a H X H tr CD o o 3 T i P c+ CD <-i T) O £W SO 3 / MICHIGAN TERMINAL SYSTEM FORTRAN G (41336) CASISO 04-18-74 00:01:26 PAGE P001 000 1 0002 0003 0 00 4. 0C05 0C06 0C07 0C08 0009 0010 001 1 0012 0013 0014 0015 0016 0017 0018 0019 0C20 002 1 0022 0 02 3 0024 0025 0026 0027 0028 0029 0030 003 1 0 03 2 0033 0034 0 03 5 0036 0037 0038 0039 0040 004 1 0042 0043 0044 0045 0046 WITH ADJACENCIES SUBROUTINE CASISO (FLADDR,PFLIP,GRAPH,GTYPE,ENDLST,NLINES,NGRAPH) C...ISOMORPHISM SCAN OVER ALL CASES FOR CURRENT GRAPH CONSTRUCTION INTEGER CONS 1 INTEGER*2 GRAPH (10,500, 16) ,GTYPE(10,5C0,32) ,ENDLST (10),TYP1(32),PP U S 1(16) ,PPTS (16) ,NLINES (10,500) IKTEGER*2 NGRAPH (10) ,PACJ1 (16),PFLIP (1C0),FLACDR(16) ,PADJ (16) ,TYP ( 132) COMMON / L I S T I S / PACJ,PACJ1,CONS1,TYP,TYP1,PPTS1, PPTS CUMMON /NUMPT/ NPTS C...COMPARE LOWER CASE GRAPHS HTTH HIGHER CASE ONES IX=CCNS1-1 IF (IX.EO.0)RETURN EC 1 J=1,IX C....FIND ALL THE GRAPHS FOR THIS CASE IY= E N DLST ( J ) - 1 I F(IY.EQ.0 )GO TO 1 EO 2 K=1,IY IF(GRAPH(J,K,1).EQ.0)GO TO 2 C . . C O M P U T E PPTS, THE SEQUENCE CF POINTS PPTS(1) = 1 IZ = 2 EC 3 L=2,NPTS IF (GRAPH (J,K,L),EQ.0)GO TO 3 PPTS(IZ)=L TZ-IZ+1 3 CONTINUE IZ=IZ-1 C....FINC HIGHER CASE GRAPHS IAZ=J+1 DO 4 L=IAZ,CONS1 IAX = ENDLST (L)-1 IF (IAX.EQ.0)GO TO 4 IFLAG4=0 DO 5 11=1,IAX IF ( (GRAPH (L,LL,1).EQ.O).OR. (NLINES (L,IL).NE. (IZ/2)))GO TO C...COMPUTE PPTS1 FOR THIS HIGHER CASE GRAPH PPTS 1 (1)=1 IW=2 DO 6 KK=2,NPTS JT=GRAPH(L,LL,KK) IF (IT.EQ.0)GO TO 6 PPTS1(IW)=KK PADJ1 (KK)=IT PAIJ1(1T)=KK IW=IWt1 6 CONTINUE IW=2*IZ tO 7 KK=1,IW TYP1 (KK)=GTYPE (L,IL,KK) 7 CONTINUE C....COMPARE LEXICOGRAPHIC TYPE IB=IZ+1 CO 10 KK=IB,IH IF (GTYPE (0,K,KK).EQ.TYP1(KK))GO TO 10 GO TO 23 436.000 437.000 > 438.000 T l 439.000 T) M 439.000 440.000 O 440.000 IH 44 1.000 X 442.000 M 443.000 444.000 i-3 445.000 IT CD 446.000 447.000 O 448.000 ompu 449.000 ompu 450.000 ompu 451.000 c+ 452.000 CD 453.000 454.000 T) 455.000 456.000 O 457.000 458.COO CD 459.000 B 460.000 46 1.000 462.COO 463.000 464.000 ' 465.000 466.000 467.000 469.000 469.000 470.000 471.000 472.000 473.000 474.000 475.000 476.000 477.000 478.000 479.000 480.000 481.000 482.000 483.000 484.000 O 485.000 4 8 6 . 0 0 0 4 8 7 . 0 0 0 4 8 8 . 0 0 0 « ICHICAN 0 04 7 0048 0049 0050 0 05.1 0052 0053 0 05.(4 0055 0056 0057 0058 0059 0060 006 1 0062 0063 0 06 4 0065 0066 0067 0068 006 9 0070 0071 0072 007 3 0074 0075 0 07 6 0077 0078 0079 0080. 0081 0082 008 3 0 08 4 0 08 5 0086 0087 0 08 8 0089 0090 0091 0092 0093 0094 009 5 0096 TERMINAL SYSTEM FORTRAN G (41336) CASISO 04- 18-74 10 C....COMPARE FORWARD • EQ.TYP1 (IJ))GO TO 13 13 17 18 19 20 17 18 16 21 C . . C . , 15 22 CONTINUE CYCLES IN REAL TYPE IFLAG1=0 DO 12 IM=1,IZ >.COMPARE TY EES DO 13 IJ=1,IZ IF (GTYPE (J.K,IJ) GO TO 15 CONTINUE .CHECK FOR ISOMORPHISM IFLAG=0 CC 16 IJ=1,IZ IIX=FPTS (IJ) IIY = C-RAPH (J,K,IIX) IIW=PPTS 1 (IJ) IIV = PACJ1 (3 I Vi) IF (IIX.GT.IIY)GC TO IIT=IIX IIX=IIY IIY=1IT IIL=IIX-IIY-1 1IH=NPTS-IIX-1+IIY IF (IIL.LE.IIHJGO TO 1 IT=IIL IIL=IIH IIH=JIT IF (IIW.GT.IIV)GO TO 19 IIT=IIW IIW=IIV 1IV=1IT IJL=IIW-IIV-1 IJH=NPTS-IIW-UIIV IF (IJL.LE.IJH)GO TO 20 IIT=IJL IJL=IJH IJH=1IT IF (IIL.EQ.IJL)GO TO 16 1FLAG= 1 GO TO 21 CONTINUE IF (IFLAG.EQ. 1)GO TO 15 GRAPHS ARE ISOMORPHIC SO CELETE HIGHER CASE GRAPH FROM LIST GRAPH (L,LL,1)=0 NGRAPH (L)=NGRAPH (L)-1 IFLAG4=1 • . •• . GO TO 23 PERMUTE CYCLES AND TRY AGAIN IIX=PETS1(1) IIY=TYP1 (1) 1IT=I7.-1 DO 22 IJ-1.IIT FFTS1 (IJ)=PPTS1 (IJ + 1) TYP 1 (IJ)=TYP1 (IJ + 1) CONTINOE PPTS1(IZ)=IIX 00:01:26 489.000 4490.000 491.000 492.000 493.000 494.000 495.000 496.000 497.000 498.000 499.000 500.000 501.000 502.000 503.000 504.000 505.000 506.000 507.000 508.000 509.000 510.000 511.000 512.000 513.000 514.000 515.000 516.000 517.000 5 18.000 519.000 520.000 521.000 522.000 •523.000 524.000 525.000 526.000 527.000 528.000 529 .000 530.000 53 1.000 532.000 533.000 5 3 4.000 535.000 536.000 . 537.000 538.COO 539.000 540.000 541.000 542.000 5*43.000 MICHIGAN TERMINAL SYSTEM FORTRAN G(41336) CASISO 04-18-7H 0 0 : 0 1 : 2 6 PAGE P003 0 09 7 0098 12 C . . . 0099 0 100 0 10 1 0102 0 103 25 0 104 0 10 5 010 6* 0 107 0 108 0 109 0110 0 111 0 112 0 113 0 114 0 115 26 0116 0117 0118 0 119 C . . . 0 120 2 3 0 12 1 0122 0 123 0 124 24 0 125 0 126 28 0 127 0 128 5 0 129 4 0 130 2 0131 1 C • • • • 0 132 0133 0 134 0135 0 136 0 137 30 0 138 013 9 FLIP GRAPH OVER TYP1 (IZ)= I IY CONTINUE AND TRY AGAIN IF( IFLAG1.EO.1)GO TO 23 IFLAG1=1 I I L = FLACCR (NPTS) CO 25 IJ=1,NPTS PADJ1 (IJ)=0 11 K= 1 DO 26 IJ=1,NPTS IIX = GRAPH ( L , L L , I J ) IF (IIX.EQ.O)GO TO 26 IIY = PFLIP ( IJ + I IL) I IX = PFLIP (I IX+IIL) PACJ1 (IIY) = I IX PADJ 1 ( I IX)=IIY IIX=PPTS1(IIH) PPTS1 (IIH) = PFLIP (IIX + I IL) IIH=IIE+1 CONTINUE CAIL SCRT (PPTS1, 1,IZ) IIX=IZ/2 CAIL GTYP (PPTS1,I IX.TYP1) GO TO 27 ZERC WORKING MATRICES DO 24 TJ=1,IZ PPTS1 (IJ)=0 TYP1(IJ)=0 TYP 1 (IJ+IZ)=0 CONTINUE DO 28 IJ=1,NPTS PAEJ1(IJ)=0 IF (IFLAG4.EQ. 1)GO TO 4 CONTINUE CONTINUE CONTINUE CONTINUE ZERO WORKING MATRICES DC 30 IJ= 1, 16 PACJ1 (IJ)=0 rPTS(TJ)=0 PFTS1 (IJ)=0 TYP1(IJ)=0 T Y P1 ( I J•16) -0 RETURN , END • OPTIONS IN EFFECT* ID,EBCDIC,SOURCE,NOLI ST,NODECK,LOAD,NOMAP •OPTIONS IN EFFBCT* NAME = CASISO , IINECNT = 57 •STATISTICS* SOURCE STATEMENTS = 139,PROGRAM SIZE => •STATISTICS* NO DIAGNOSTICS GENEHATEC 544 545 547 548 54 9 550 55 1 552 553. 554. 555 . 556. 557 . 558. 559. 560. 56 1. 562. 563 . 564. 5 6 5 . 566. 56 7 . 568. 569 . 570. 5 7 1 . 572. 573 . 574. 576. 5 7 7 . 578. 579. 580. 58 1. 582. 583. 584. 585 . 586. 587. 588. 589. 590. 59 1. .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 .000 coo .COO coo .000 .000 .000 .000 .coo .000 .000 .000 .000 coo coo 000 OCO 000 000 000 coo 000 000 000 000 000 000 000 000 000 .S3 a M fx! t-3 i? CD o o 3 Xi p ct CD Tt o cn <-i 3 33 30 ro MICHIGAN TERMINAL SYSTEM FORTRAN G (41336) SORT 04- 18-74 0C01 SUBROUTINE SORT(II,IA,IE) C....TO SORT A LINEAR LIST OF INTEGERS 0002 INTEGER*2 IL (35) 000 3 IKCX1=IH-1 0004 CC 1 J= IA , IN DX 1 C. ... INTERCHANGE WITH SMALLEST ELEMENT IN THE REST OF THE LIST 0005 IK=J 0006 IKIN = IL (.1) 0007 Ii;EX2 = J+1 0008 DO 2 K=INDX2,IB 0009 IF (IMIN.LE.IL (K))GC TC 2 0010 IMIN=IL(K) 0011 IK=K 0012 2 CONTINUE 0013 IF (IK.EQ.O)GO TO 1 0014 I X= IL (J) 0015 Il(J)=IKIN 0016 IL(TK)=IX 0017 1 CONTINUE 0018 RETURN 0019 ENC • OPTIONS IN EFFECT* ID,EBCDIC,SOUHCE,NOLI ST,NODECK,LOAD,NOMAP • OPTIONS IN EFFECT* NAME = SORT , LIN EC NT = 57 •STATISTICS* SOURCE STATEMENTS = 19,PROGRAM SIZE = 610 •STATISTICS* NO C1AGNOSTICS GENERATEC NO STATEMENTS FLAGGED IN THE AEOVE COMPILATIONS. $SIG 01:29 592.000 593.000 594.000 595.000 596.000 597.000 598.000 599.000 600.000 601.000 602.000 603.000 604.000 605.000 606.000 607.000 608.000 609.COO 610.000 611.000 612.000 PAGE P001 > Tl TJ K a H t—i •-3 fl) O O B c+ CD T3 o APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,&12 Point s 74 The edges of the 1-factors of the graphs are given below. A basic n-cycle of 1-2-3-4-...-n-1 i s assumed. _ _ _ i _ _ 2 _ _ _ _ _____ Graphs on 6 P o i n t s 1. 1-3 2-5 4-6 2. 1-4 2-5 3-6 Hamiltonian Cubic Graphs on 8 P o i n t s 1. 1-3 2-6 4-7 5-8 2. 1-3 2-7 4-6 5-8 3. 1-3 2-8 4-6 5-7 4. 1-4 2-6 3-7 5-8 5. 1-4 2-7 3-6 5-8 _ _ _ i _ _ 2 _ i _ _ _____ Graphs on W P o i n t s 1. 1-3 2-8 4-6 5-9 7-10 2. 1-3 2- 10 4-6 5-8 7-9 3. 1-3 2-7 4-8 5-9 6-10 1-3 2-7 4-10 5-8 6-9 5. 1-3 2-8 4-9 5-7 6-10 6. 1-3 2-8 4-10 5-7 6-9 7. 1-3 2-9 4-10 5-7 6-8 8. 1-3 2- 10 4-7 5-8 6-9 9. 1-3 2-10 4-9 5-7 6-8 10. 1-3 2-8 4-6 5-10 7-9 APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,512 Point s 11. 1-3 2-9 4-6 5-8 7-10 12. 1-3 2-8 4-7 5-10 6-9 13. 1-4 2-9 3-6 5-8 6-10 14. 1-4 2-7 3-9 5-8 6-10 15. 1-4 2-7 3-10 5-8 6-9 16. 1-4 2-9 3-7 5-8 6-10 17. 1-4 2-8 3-7 5-10 6-9 18. 1-4 2-7 3-8 5-9 6-10 Hamiltonian Cubic Graphs on 12 Poi n t s 1. 1-3 2-11 4-6 5-7 8-10 9-12 2. 1-3 2-12 4-6 5-7 8-10 9-11 3. 1-3 2-6 4-10 5-7 8-11 9-12 4. 1-3 2-8 4-12 5-7 6-10 9-11 5. 1-3 2-9 4-10 5-7 6-11 8-12 6. 1-3 2-9 4-12 5-7 6-10 8-11 7. 1-3 2-10 4-7 5-8 6-11 9-12 8. 1-3 2-10 4-9 5-7 6-12 8-11 9. 1-3 2-11 4-12 5-7 6-9 8-10 10. 1-3 2-12 4-9 5-7 6-10 8-11 11. 1-3 2-8 4-6 5-11 7-9 10-12 12. 1-3 2-9 4-6 5-10 7-11 8-12 13. 1-3 2-10 4-6 5-11 7-9 8-12 14. 1-3 2-10 4-6 5-12 7-9 8-11 15. 1-3 2-11 4-6 5-8 7-9 10-12 APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,612 Po i n t s 16. 1-3 2-11 4-6 5-9 7-10 8-12 17. 1-3 2-11 4-6 5-12 7-9 8-10 18. 1-3 2-12 4-6 5-9 7-10 8-11 19. 1-3 2-12 4-6 5-11 7-9 8-10 20. 1-3 2-8 4-7 5-10 6-11 9-12 21. 1-3 2-8 4-9 5-11 6-10 7-12 22. 1-3 2-8 4-10 5-9 6-12 7-11 23. 1-3 2-8 4-10 5-11 6-9 7-12 24. 1-3 2-8 4-10 5-12 6-9 7-11 25. 1-3 2-8 4-12 5-9 6-10 7-11 26. 1-3 2-8 4-12 5-10 6-9 7-11 27. 1-3 2-8 4-12 5-11 6-9 7-10 28. 1-3 2-9 4-7 5-10 6-11 8-12 29. 1-3 2-9 4-8 5-11 6-10 7-12 30. 1-3 2-9 4-10 5-11 6-8 7-12 31. 1-3 2-9 4-12 5-10 6-8 7-11 32. 1-3 2-9 4-12 5-11 6-8 7-10 33. 1-3 2-10 4-9 5-12 6-8 7-11 34. 1-3 2-10 4-11 5-8 6-9 7-12 35. 1-3 2-10 4-12 5-8 6-9 7-11 36. 1-3 2-10 4-12 5-9 6-8 7-11 37. 1-3 2-10 4-12 5-11 6-8 7-9 38. 1-3 2-11 4-10 5-12 6-8 7-9 39. 1-3 2-11 4-12 5-8 6-9 7-10 40. 1-3 2-11 4-12 5-9 6-8 7-10 APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,512 Point s 41. 1-3 2-11 4-12 5-10 6-8 7-9 42. 1-3 2-12 4-7 5-9 6-10 8-11 43. 1-3 2-12 4-8 5-10 6-9 7-11 44. 1-3 2-12 4-8 5-11 6-9 7-10 45. 1-3 2-12 4-9 5-8 6-11 7-10 46. 1-3 2-12 4-10 5-11 6-8 7-9 47. 1-3 2-12 4-11 5-8 6-9 7-10 48. 1-3 2-12 4-11 5-10 6-8 7-9 49. 1-3 2-8 4-10 5-7 6-12 9-11 50. 1-3 2-11 4-10 5-7 6-9 8-12 51. 1-3 2-12 4-9 5-7 6-11 8-10 52. 1-3 2-8 4-7 5-11 6-10 9-12 53. 1-3 2-8 4-10 5-11 6-12 7-9 54. 1-3 2-8 4-12 5-11 6-10 7-9 55. 1-3 2-9 4-7 5- 12 6-11 8-10 56. 1-3 2-9 4-12 5-8 6-11 7-10 57. 1-4 2-7 3-10 5-8 6-11 9-12 58. 1-4 2-8 3-9 5-10 6-11 7-12 59. 1-4 2-8 3-10 5-9 6-11 7-12 60. 1-4 2-8 3-11 5-9 6-10 7-12 61. 1-4 2-8 3-12 5-9 6-10 7-11 62. 1-4 2-9 3-8 5-10 6-11 7-12 63. 1-4 2-10 3-7 5-8 6-11 9-12 64. 1-4 2-10 3-12 5-8 6-9 7-11 65. 1-4 2-11 3-8 5-9 6-10 7-12 APPENDIX I I Hamiltonian Cubic Graphs on 6,8,10,S12 Points 66. 1-4 2-11 3-9 5-8 6-10 7-12 67. 1-4 2-11 3-10 5-8 6-9 7-12 68. 1-4 2-11 3-12 5-8 6-9 7-10 69. 1-4 2-6 3-11 5-9 7-10 8-12 70. 1-4 2-7 3-10 5-9 6-11 8-12 71. 1-4 2-8 3-9 5-12 6-10 7-11 72. 1-4 2-8 3-10 5-11 6-7 7-12 73. 1-4 2-10 3-9 5-8 6-12 7-11 74. 1-4 2-8 3-9 5-12 6-11 7-10 75. 1-4 2-9 3-8 5-12 6-11 7-10 76. 1-5 2-8 3-11 4-9 6-10 7-12 77. 1-5 2-9 3-11 4-8 6-10 7-12 78. 1-5 2-8 3-9 4-11 6-10 7-12 79. 1-3 2-12 4-11 5-7 6-9 8-10 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051754/manifest

Comment

Related Items