Cycles and Bridges in Graphs. (= Mathematische Monographien, 23).

by Hans-Juergen Voss

Since the first book on graph theory by D.Kőnig appeared in 1936, this branch of mathematics has enormously developed. This is true for both the theory and the applications to many problems of practical interest. The study of properties of bridges of certain subgraphs yields interesting results in various fields, especially in constructing graph theoretical algorithms. The book is devoted to cycles and bridges in (finite, undirected, simple) graphs, particularly to bridges of cycles. The emphasis of the book is on the concept of bridge. This concept was first introduced by Tutte and Ore and and is now widely used in graph theory. In chapter 1 overlap graphs (bridge graphs) are introduced and their applications to planar & non-planar graphs are treated (Kuratowski's theorem, Hamiltonian cycles in planar graphs etc). Graphs whose cycles (or paths) have only one bridge are investigated in chapter 2. Chapter 3 is concerned with intersection patterns of longest cycles. Upper bounds for the circumference of bridges of longest cycles are determined. Ch. 4-6 are devoted to graphs with high symmetries, i.e., with many isomorphic bridges. The obtained results are applied to critical graphs. The Reconstruction problem is solved for some classes of such highly symmetric graphs. Chapters 7-11 are concerned with valency conditions and conditions on the number of edges for the existence of long cycles through given vertices and edges and for the existence of cycles with many diagonals. In chapters 9-10 the girth of the graphs is involved. All cubic graphs with given circumference having maximum order are determined in chapter 11. This monograph finishes with a large bibliography which gives a survey on publications to this topic up to now. The level of development of the theory is the reason enough for writing this monograph which shows once more that graph theory is undoubtedly one of the simplest and most elegant mathematical subjects possessing a wide variety of applications.

271 pages, Hardcover

First published August 31, 1991