zbMATH — the first resource for mathematics

Cycles and bridges in graphs. (English) Zbl 0731.05031
This book is a self-contained and highly readable work on cycles and bridges in graphs. All graphs considered in the volume are simple and finite. Let J be a subgraph of a given graph G. Loosely speaking the bridges of J in G are the minimal subgraphs that are attached to the remainder of G at vertices of J. For this concept different names are also used by different authors (J-component, J-fragment, piece, etc.). Next concept dealt with is the overlap graph 0(G:C) of a grah G with respect to a cycle C. The vertices of 0(G:C) are the bridges of C where two vertices are joined by an edge if the corresponding bridges overlap. Further, the author presents results of Kelmans, McLane and Tutte on separating and non-separating cycles. A cycle is called separating if it has at least two regular bridges. A study is also made of the “length” and the cirsumference of bridges. Three chapters mainly deal with isomorphic bridges (in 2-connected graphs with a given circumference, graphs with “many” isomorphic bridges, applications to critical graphs). Further the author investigates valency conditions for the existence of long cycles having certain properties. One of the pioneering results is the well-known theorem of Dirac (1952) on Hamiltonian cycles. A diagonal of a subgraph H in G is an edge of G not in H joining two vertices of H. An important result presented here is that, except for three graphs, every non-bipartite 2-connected graph G with minimum valency at least 3 contains both an odd and an even cycle with two or more diagonals. Another result on such a graph G with girth t at least 4 says that G contains both an odd and an even cycle of length at least \(2^{(t/4)-7}\) and both an odd and even cycle with at least \(2^{(t/12)-8}\) diagonals. Finally, the author turns out to some problems of the extremal graph theory (long cycles with “many” diagonals, longest cycles in graphs of given maximum valency). The volume is rounded off by an extensive bibliography.

05C38 Paths and cycles
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C35 Extremal problems in graph theory