Some aspects of graph theory

Abstract

This thesis embodies most of the research I have undertaken since the completion of my Ph.D. dissertation in 1972. It seems appropriate, and is indeed a pleasure, at this point to acknowledge the influences of others on my work over the years. My interest in graph theory was originally stimulated in 1968 by Alfred Lehman, who supervised my masterate at the University of Toronto. The resulting thesis consisted of the development and implementation of an algorithm for testing the planarity of a graph. Although this masterate was in computer science, I realised that it was the mathematical aspects of the work that most interested me. Consequently I enrolled for a doctorate in graph theory at the University of Waterloo, where I studied under the supervision of Dan Younger. There I focussed on 1-factors of graphs, investigating in particular Kasteleyn's method for enumerating them. I attempted to characterise those graphs for which Kasteleyn's method succeeds. Since the method was known to succeed for planar graphs, this work was not far removed from my earlier interest in planarity. Consequently the two themes of topological graph theory and matchings in graphs were prominent from the early stages of my research career. Following the completion of my degree at the University of Waterloo, in 1973 I secured an appointment at the Royal Melbourne Institute of Technology Ltd. Here I had the great good fortune to be in contact with Derek Helter, now a professor at the University of Otago. His office at the University of Melbourne was only about a 15-minute walk from my own, and we often worked together. I interested him in my ideas on planarity and together we succeeded in discovering a characterisation of planar graphs. Alas Chernyak, working in Russia, beat us to that result, but by the time his proof appeared Derek and I were already collaborating on a generalisation. Derek was really a mentor for me at that early stage in my career, and I owe him a great deal. My interests in topological graph theory and 1-factors of graphs have been maintained since my arrival at Massey University in 1982. My collaborators since that time have included my masterate student Janet McCall, doctoral students Paul Bonnington, Allister Campbell and Serguei Norine and postdoctoral fellows Hong Wang and Feng Ming Dong. With Paul I wrote my first book, The Foundations of Topological Graph Theory. Dong inspired many of us in the mathematics discipline at Massey with his enthusiasm for chromatic polynomials, and this topic became a third theme in my research. More recently I have collaborated with Bruce van Brunt and Kee Teo in writing a second book, The Number Systems of Analysis. Of my other collaborators, special mention should be made of Ilse Fischer, with whom I worked at the University of Klagenfurt during my period of study leave in 1999. Together with her I characterised Pfaffian near bipartite graphs, and this result represents what is probably my best work.