Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Graph theory and its applications (3rd ed.)
Gross J., Yellen J., Anderson M., Chapman&Hall/CRC, Boca Raton, FL, 2018. 591 pp.  Type: Book (978-1-482249-48-4)
Date Reviewed: Oct 23 2019

Graph theory is one of the most fertile and popular domains in current mathematics research. This is mainly because graphs can be used as coherent models for many problems across almost all disciplines. This book can be viewed as effective and authentic material for budding learners of graph theory at a collegiate level.

The book consists of 11 chapters. The first chapter covers the basic terminology of graphs, including the basic graph families and their properties. Highlights include discussions on more than a dozen applications of graphs in real-life situations. The second chapter explores structural characteristics and representations. The first section of chapter 2 discusses in detail the concepts of structural equivalence of graphs, including graph isomorphism, graph automorphism, and vertex and edge transitivity. Next, it provides different types of subgraphs and their applications. Later in the chapter, the authors provide the terminology and results for different graph operations and graph products. They also define the different types of matrices associated with graphs.

The third chapter goes into the terminology of trees: connected graphs without cycles. It starts with the significant characterizations of different types of trees. Following this introductory section, the authors describe tree-searching methods with corresponding algorithms, the application of trees and tree searching to coding theory, and counting techniques. The fourth chapter is a continuation of chapter 3. It begins with the concept of tree growing, its applications, and related algorithms such as the depth-first search (DFS) algorithm, the breadth-first search (BFS) algorithm, spanning tree algorithms, and shortest path algorithms. The highlight of this chapter is its discussion of vector spaces associated with graphs. This topic includes the notions and results on cycle space and edge-cut space; their bases, dimensions, and orthogonality properties; and so on.

The fifth chapter discusses connectivity in graphs. It includes the terminology of a vertex and connectivity, their relationship, related characterizations and constructions, duality, optimizations, and so on. The last section of this chapter discusses the block decomposition of graphs. Chapter 6 discusses well-known graph traversal problems; Eulerian and Hamiltonian graphs and their characterizations; algorithms to determine Euler tours and Hamiltonian cycles, and their applications in real-life/practical problems; and so on. Chapter 7 covers planarity and related results. It also explains Kuratowski’s theorem, algebraic tests for planarity, algebraic proofs for nonplanarity, planarity check algorithms, crossing numbers and thickness, and more.

Graph coloring, a well-known and popular topic in graph theory, is discussed in detail in chapter 9. It includes topics such as vertex coloring, edge coloring, map coloring, corresponding chromatic numbers, coloring algorithms, and the criticality of graph coloring. At the end of the chapter, the authors discuss the factorization of graphs and related theorems. While chapter 9 describes how graphs and digraphs are used to model certain problems, chapter 10 discusses graph theoretical interpretations and the analysis of network flows in terms of connectivity and flow. The final chapter of the book, as an extension of chapter 9, explores the relationship between the symmetry of the graph and graph coloring.

This is a worthy book for many reasons. First and most importantly, its presentation style introduces concepts with the support of ample illustrations and diagrams. The second aspect is the careful and precise selection of topics. The transition from one chapter to the next is smooth and effortless. Another commendable point is its beautiful and algorithmic approach to the topics. For all these reasons, the book is a perfect choice for beginners in graph theory.

Reviewer:  Sudev Naduvath Review #: CR146741 (2002-0016)
Bookmark and Share
  Reviewer Selected
Graph Theory (G.2.2 )
Would you recommend this review?
Other reviews under "Graph Theory": Date
Attention models in graphs: a survey
Lee J., Rossi R., Kim S., Ahmed N., Koh E.  ACM Transactions on Knowledge Discovery from Data 13(6): 1-25, 2019. Type: Article
Sep 20 2021
Recognizing weak embeddings of graphs
Akitaya H., Fulek R., Tóth C.  ACM Transactions on Algorithms 15(4): 1-27, 2019. Type: Article
Mar 12 2021
Exact transversal hypergraphs and application to Boolean -functions
Eiter T.  Journal of Symbolic Computation 17(3): 215-225, 1994. Type: Article, Reviews: (2 of 2)
Nov 26 2020

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy