×

Pearls in graph theory. A comprehensive introduction. (English) Zbl 0703.05001

Boston etc.: Academic Press, Inc. ix, 246 p. $ 29.95 (1990).
The book under review is intended for undergraduate students. It is self- contained and assumes only a good knowledge of high school mathematics. Most of the time the authors work with finite simple graphs but multigraphs and pseudographs are also introduced. Infinite graphs are considered only in one section. Among other things the book concerns the following topics: Havel’s theorem on graphic sequences, chromatic numbers, Hamilton cycles and Hamilton paths, Königsberg bridge problem and Eulerian circuits, decompositions of cubic graphs, Hamilton lines in an infinite graph, Turán’s theorem, Ramsey numbers, counting spanning trees of a graph, magic graphs and graceful trees, algorithmic approach to spanning trees, some properties of planar graphs, crossing numbers and other measurements of closeness to planarity, embedding graphs on other surfaces, genus of a graph, etc. Difficult or long proofs are often omitted. For instance, Vizing’s theorem on the chromatic index, Zhang’s theorem on cubic subgraphs in a regular graph of degree four and Kuratowski’s theorem on the planarity of graphs are presented without proofs. Needless to say that the Four Color Theorem is here without any sketch of proof. Among curiosities collected by the authors in this volume let us mention what they call Ringel’s Icosahedron, i.e. a straight line embedding with 19 triangles having the same area. Each section of the book is followed by a suitable portion of exercices. Many of them are routine.
{At the conference in Smolenice (1963) the reviewer proposed a problem of characterizing magic graphs and also showed that the cube and octahedron are prime-magic [Theory of graphs and its applications, Academic Press 1964, Problem 27, pp. 163-164]. On p. 103 of the book under review one finds a picture which is identical with reviewer’s example showing prime-magic valuation of the cube. The authors call it Steward’s cube. Notice that the second author attended 1963 the conference in Smolenice.}
Reviewer: J.Sedláček

MSC:

05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05Cxx Graph theory
PDFBibTeX XMLCite

Online Encyclopedia of Integer Sequences:

Alternate Lucas numbers - 2.