Graph theory with applications.

*(English)*Zbl 1226.05083
New York, NY: American Elsevier Publishing Co. x, 264 p. (1976).

This is the best book dealing with various applications of graph theory that has appeared yet. Being the most recent book on the theory of graphs, it also contains some results that are more current than those in any other existing book.

From the preface: “The applications appearing at the end of each chapter actually make use of theory developed earlier in the same chapter. We also stress the importance of efficient methods of solving problems. Several good algorithms are included and their efficiencies are analysed. We do not, however, go into the computer implementation of these algorithms.” The authors make no claim to present a comprehensive overview of graph theory and have chosen to omit almost entirely such intriguing topics as the interaction between and mutual applicability of graphs and groups, and of graphs and matrices. However, they have included proofs of almost every theorem stated in the book, and several of these are new and elegant – some being due to the work of Lászlo Lovász. In the opinion of the reviewer, it is unfortunate that graphs are defined to admit both multiple edges and loops. The authors’ “simple graph” is the more conventional “graph”, and their “strict digraph” is the usual “digraph”. De gustibus non disputandum.

It is more unfortunate that the authors occasionally alter generally accepted notation and terminology–this cannot help but cause some confusion. Among others, they have changed a “strong” digraph (strongly connected) to a “diconnected” digraph and a “strong component” to a “dicomponent”, and “totally disconnected” graph (or better “discrete”) to “empty” graph.

The accuracy and completeness of the references is not always satisfactory. On pp. 7 and 24 (Frucht, 1939) should be (Frucht, 1938). On p. 143, ex. 9.2.8 is attributed to the reviewer and D. W. Matula but no references are given. A relevant paper by Matula has been published [SIAM J. Appl. Math. 22 (1972), 459–480; Zbl 0243.05111 ], and the work of the reviewer is joint with D. Hsu and Z. Miller (J. Graph Theory, to appear). The answer to the question of ex. 10.1.1 on p. 173, “How many orientations does a simple graph \(G\) have?” was given in a paper by the reviewer and E. M. Palmer [Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 14 (1966), 125–128; Zbl 0135.42105], but no reference is given. Further, this exercise number is not even in bold face – let the reader beware. The concept of uniquely colorable graphs in ex. 8.1.8, p. 121, was first introduced by D. Cartwright and the reviewer [Elem. Math. 23 (1968), 85–89; Zbl 0155.31703]; again no reference is given. These are just a few of the examples – several others can be cited. It is a pity that references are given only at the end of each chapter and not compiled together for easier accessibility.

Returning to the positive, the expositions of matchings and edge coloring in Chapters 5 and 6 are outstanding. Appendix III, which presents both the diagrams and properties of “some interesting graphs” is delightful. All things considered, it is the high quality and importance of the applications which make this a most welcome book. Every chapter includes at least one application, and the list is impressive: the shortest path problem; Sperner’s lemma; the connector problem; construction of reliable communication networks; the Chinese postman problem; the traveling salesman problem; the personnel assignment problem; the optimal assignment problem; the timetabling problem; a geometry problem; a storage problem; a planarity algorithm; ranking the participants in a tournament; feasible flows; and perfect squares. Also, the book is remarkably free of misprints.

From the preface: “The applications appearing at the end of each chapter actually make use of theory developed earlier in the same chapter. We also stress the importance of efficient methods of solving problems. Several good algorithms are included and their efficiencies are analysed. We do not, however, go into the computer implementation of these algorithms.” The authors make no claim to present a comprehensive overview of graph theory and have chosen to omit almost entirely such intriguing topics as the interaction between and mutual applicability of graphs and groups, and of graphs and matrices. However, they have included proofs of almost every theorem stated in the book, and several of these are new and elegant – some being due to the work of Lászlo Lovász. In the opinion of the reviewer, it is unfortunate that graphs are defined to admit both multiple edges and loops. The authors’ “simple graph” is the more conventional “graph”, and their “strict digraph” is the usual “digraph”. De gustibus non disputandum.

It is more unfortunate that the authors occasionally alter generally accepted notation and terminology–this cannot help but cause some confusion. Among others, they have changed a “strong” digraph (strongly connected) to a “diconnected” digraph and a “strong component” to a “dicomponent”, and “totally disconnected” graph (or better “discrete”) to “empty” graph.

The accuracy and completeness of the references is not always satisfactory. On pp. 7 and 24 (Frucht, 1939) should be (Frucht, 1938). On p. 143, ex. 9.2.8 is attributed to the reviewer and D. W. Matula but no references are given. A relevant paper by Matula has been published [SIAM J. Appl. Math. 22 (1972), 459–480; Zbl 0243.05111 ], and the work of the reviewer is joint with D. Hsu and Z. Miller (J. Graph Theory, to appear). The answer to the question of ex. 10.1.1 on p. 173, “How many orientations does a simple graph \(G\) have?” was given in a paper by the reviewer and E. M. Palmer [Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 14 (1966), 125–128; Zbl 0135.42105], but no reference is given. Further, this exercise number is not even in bold face – let the reader beware. The concept of uniquely colorable graphs in ex. 8.1.8, p. 121, was first introduced by D. Cartwright and the reviewer [Elem. Math. 23 (1968), 85–89; Zbl 0155.31703]; again no reference is given. These are just a few of the examples – several others can be cited. It is a pity that references are given only at the end of each chapter and not compiled together for easier accessibility.

Returning to the positive, the expositions of matchings and edge coloring in Chapters 5 and 6 are outstanding. Appendix III, which presents both the diagrams and properties of “some interesting graphs” is delightful. All things considered, it is the high quality and importance of the applications which make this a most welcome book. Every chapter includes at least one application, and the list is impressive: the shortest path problem; Sperner’s lemma; the connector problem; construction of reliable communication networks; the Chinese postman problem; the traveling salesman problem; the personnel assignment problem; the optimal assignment problem; the timetabling problem; a geometry problem; a storage problem; a planarity algorithm; ranking the participants in a tournament; feasible flows; and perfect squares. Also, the book is remarkably free of misprints.

Reviewer: F. Harary (MR0411988)