Fleischner H. Eulerian Graphs and Related Topics

North-Holland, 1990-1991. — 738 p.Since writing my Ph.D. thesis, Hamiltonian and Eulerian graph theory have been the main topics of my research. Until 1975 I put more emphasis on Hamiltonian graph theory; since then, however, problems in Eulerian graph theory and related questions have been central to my work. This shift in research emphasis from Hamiltonian to Eulerian graphs was initiated by a problem posed to me by Gert Sabidussi (Universite de Montreal) in the summer of 1975 when I was in Montreal undertaking joint research with him. At that time neither Sabidussi nor I could foresee the relatively wide range of applications that a solution to his problem (henceforth called Sabidussi's conjecture) would have.
During the academic year 1976/77 I was able to prove a generalization of Sabidussi's conjecture for planar eulerian graphs (henceforth called the compatibility result); from 1979 onwards, a series of various applications in the theory of planar graphs were discovered (partly just by myself, partly in co-operation with Bill Jackson, the 'Chinese Postman' Guan Meigu, and - recently - Andras Frank). In the course of these discoveries, it transpired that in various proofs, the application of the Four-Color Theorem (or the assumption of the validity of the Four-Color Conjecture, if you wish) could be avoided by using the compatibility result. ^
Unfortunately, there is no simple analogy to the compatibility result in the case of non-planar graphs, however, in recent joint work with Bill Jackson we have put forward a conjecture which contains as a specialcase an equivalent formulation of the cycle-double-cover conjecture. This and the preceding statements indicate why Sabidussi's conjecture and generalizations thereof, but also its solution in the planar case (we call this whole complex of conjectures and results the compatibility problem), as well as its applications and implications, assume a dominant position in the second part of the book.
The academic year 1977/78 was proclaimed graph theory year at the Department of Mathematics at Memphis State University (MSU), Tennessee. Following an invitation by R. Faudree and R. Schelp I spent the fall semester there, during which I gave a three-hour course on Eulerian graph theory. At that time I was familiar with A. Kotzig's work in that field of research, and, apart from the compatibility problem I had done research on a special type of Eulerian trails which had been extended by my first Ph.D. student S. Regner. In presenting the material at MSU, it occurred to me for the first time that as a topic Eulerian graphs constituted more than a mere accumulation of results. Tendencies towards the development of theories on Eulerian graphs became visible for me. Consequently, when I learned from L.W. Beineke and R.J. Wilson at the graph theory meeting in Oberwolfach in 1979, that they were preparing Selected Topics in Graph Theory 2 ([BEIN83a]), I asked them if they were interested in a survey article on Eulerian graphs. They doubted whether there was sufficient material to justify such an article, but agreed that I should try to write a contribution to [BEIN83a]. In preparing this survey article I was astonished to learn how much material had in fact accumulated on the subject Eulerian Graphs and Related Topics. By 1980, a first version of the survey article Eulerian Graphs was ready; after a first criticism by the editors of [BEIN83a], we agreed that I should write a second extended version from which the editors would produce a condensed version (which finally appeared in [BEIN83a]). This extended version was 90 typewritten pages long (ten of which were taken up by a bibliography using 124 references).
After the 90-page version of Eulerian Graphs (originally named Towards Theories on Eulerian Graphs) had been delivered to the editors of [BEIN83a], it occurred to me that there was enough material to justify writing a book on Eulerian Graphs and Related Topics that would be four to five times as long. This book is the result of checking further into the literature which has become available during the first half of the eighties. Its structure follows partly that of the survey article Eulerian Graphs as presented in [BEIN83a] (with some chapters added and greater emphasis added to others).VOLUME 1Three Pillars of Eulerian Graph Theory.
Basic Concepts and Preliminary Results.
Characterization Theorems and Corollaries.
Euler Revisited and an Outlook on Some Generalizations.
Various Types of Eulerian Trails.
Transformations of Eulerian Trails.
VOLUME 2
Various Types of Closed Covering Walks.
Eulerian Trails - How Many?
Algorithms for Eulerian Trails and Cycle Decompositions. Maze Search Algorithms.