Graph theory and its applications.

*(English)*Zbl 0920.05001
CRC Press Series on Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press. 585 p. (1999).

The time has now come that graph theory should be part of the education of every serious student of mathematics and computer science. This book is suitable for classroom presentation at the introductory graduate or advanced undergraduate level, or for self-study and reference. It is devided into 15 chapters, and every chapter has several subheadings. Chapters 1 through 7 concentrate on modeling, representation, graph operations and basic properties. Chapters 8 and 9 deal with drawing graphs (maps) on surfaces. Chapter 10 considers colouring the vertices (faces) and edges of a (planar) graph. Oriented graphs (digraphs) are considered in Chapters 11 and 12. Chapter 13 develops the basic concepts and tools for the counting of graphs. Chapter 14 considers a more recent notion, the voltage graph, i.e. a vertex-labeled digraph whose edges are labeled by algebraic elements. In Chapter 15 voltage graphs are used, among others, to find the solution of Heawood’s problem.

Most of the material in Chapters 1 through 7 assumes no prerequisite. The five appendices provide a quick survey for some of the more advanced topics in the later chapters. Every chapter contains a glossary viewing basic notions. Emphasis throughout is conceptual, with more than 750 excellent graph drawings and an unusually large number of well-thought-out exercises, over 1600 in total. Algorithms are written in a concise format and computer science students can easily use them to convert algorithms to computer programs.

Most of the material in Chapters 1 through 7 assumes no prerequisite. The five appendices provide a quick survey for some of the more advanced topics in the later chapters. Every chapter contains a glossary viewing basic notions. Emphasis throughout is conceptual, with more than 750 excellent graph drawings and an unusually large number of well-thought-out exercises, over 1600 in total. Algorithms are written in a concise format and computer science students can easily use them to convert algorithms to computer programs.

Reviewer: J.Fiamčik (Prešov)