The symmetry of graphs
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
The history of graphs goes back to the work of Eulerin his discovery of the equation f – e + v = 2 relating the number of faces, edges and vertices of a polyhedron and his treatment of the puzzle of the bridges of Königsberg. Thereafter it grew only slowly, with a paper by Jordan in 1869 and then a number of papers by Cayley. About the beginning of this century it began to attract numbers of workers, frequently to investigations connected more or less closely with the still-unsolved four-colour problem. In 1936 the first book devoted to graph theory appeared (König – Theorie der endlichen und unendlichen Graphen) but there was no book in English until the translation of Berge's book in French was published in 1962. A few other books in English have appeared since. It was chance coming of Berge's book into my hands that really determined me to research in the theory of graphs, and my interest in groups and algebra in general that determined that I should make the main subject of this thesis the symmetry of graphs. Chapter 1 is devoted to establishing a foundation of graph theoretical concepts and results. Apart from the omission, on the grounds of space, of the proofs of some of the simpler results, it has been my aim to make this thesis self-contained as far as the graph-theory is concerned. I have made no such attempt with regard to any algebra or topology I may have used. At the most I have cited references. Chapter 2 devoted to automorphism properties of graphs. It includes parts that are well-known and also a considerable proportion of my own researches. These will be indicated in that place. Chapter 3 recounts briefly the results obtained on the symmetry of graphs in researches that have come to my notice. Those few portions which are my own are again indicated. The remaining chapters are almost entirely my own. The problem of embedding a graph in a surface, scarcely mentioned here, has been discussed in some few papers by Harary and others, but no-one seems to have considered the problems of symmetric embedding of graphs.