Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Basic graph theory
Rahman M., Springer International Publishing, New York, NY, 2017. 169 pp. Type: Book (978-3-319494-74-6)
Date Reviewed: Jan 9 2018

Graph theory is a branch of discrete mathematics that has numerous theoretical and practical applications in a wide variety of areas. In this book, the author presents the fundamental concepts and terminology of graph theory in a simple, straightforward, and effective manner. Similar to many other books on graph theory, this book also discusses certain practical applications and basic terminology of graph theory in its initial chapters.

In the first chapter, some well-known practical problems such as utility distribution, floor planning frequency assignments, and map coloring are discussed, and the author explains how these problems can be modeled using graphs. In addition to these common problems, certain problems such as phylogenetic analysis, genome ontology, taxonomic trees in bioinformatics, problems in web communities, and soft engineering are also mentioned.

Chapter 2 deals with the fundamental terminologies of graph theory. Basic definitions of graphs, subgraphs, different fundamental graph classes, graph operations, graph isomorphism, and so on are covered. The final part of the chapter includes the description of different matrices related to given graphs and related graph representations such as the adjacency matrix, the incidence matrix, and the adjacency list.

Chapter 3 discusses the connectivity and traversability of graphs. Basic concepts of paths, cycles, connected and disconnected graphs, Eulerian graphs, and Hamiltonian graphs are explained. Necessary and sufficient conditions for a graph to be bipartite, Eulerian, and Hamiltonian are also described. The notions of 2-connected graphs, cut-vertex trees, ear decompositions of graphs, and related results are the highlights of this chapter.

In chapter 4, the author describes the notion and properties of trees. The terminology of spanning trees of given graphs and rooted trees is also included in this chapter. Cayley’s theorem on labeled trees (the result of which describes the number of labeled trees on n vertices), certain results on distances and center of trees, and Kruskal’s algorithm for minimal spanning trees of graphs are the other major topics in this chapter. The terminology of graceful labeling of graphs is also introduced.

Topics in matching and coverings of graphs are discussed in chapter 5. Besides the related graph parameters like matching number and covering number, the concepts of domination in graphs and factors in graphs are also introduced.

In chapter 6, the terminology and characterization of planar graphs (Kuratowski’s theorem, without proof) are described. A Euler formula of a planar graph, connecting its order, size, and number of faces, is proven, and an inequality connecting the order and size of a planar graph is also established. At the end of the chapter, the existence of a straight-line joining for every planar graph is established.

The concepts and results on graph coloring are discussed in chapter 7. Brooke’s theorem (which states that every simple graph has a (Δ+1)-coloring), the five-color theorem (which states that every planar graph is 5-colorable), a small description on chromatic polynomials, and a note on the four-color conjecture are included in this chapter. The notion of acyclic coloring, which is not included in many other books meant for college students, is also found here.

Topics on directed graphs are included in chapter 8. Characterization of Eulerian digraphs, results on Hamiltonian digraphs, and tournaments are also covered. The chapter also contains the terminology of flow networks and the max-flow min-cut theorem.

The highlights of the book are chapters 9 and 10. The first topic in chapter 9 consists of the notion of outerplanar graphs and their characterizations. The second major topic in the chapter is triangulated plane graphs, their canonical ordering, separating triangles, plane 3-trees, and related results. The other topics in this chapter are chordal graphs and their characterization, interval graphs and their characterization, and series-parallel graphs.

The last chapter consists of some research topics in graph theory. The first half contains the description of graph representations (computer inputs); related complexities and graph-drawing techniques such as straight-line drawing, convex drawing, orthogonal drawing, point-set embedding, simultaneous embedding, and so on of planar graphs; and right-angle-crossing (RAC) drawing and bar k-visibility drawing of nonplanar graphs. The descriptions of graph labeling and graph partitioning techniques follow. The most innovative and interesting part of the chapter is the description of graph models in bioinformatics problems such as the Hamilton path for DNA sequencing, cliques for protein structure analysis, and pairwise compatibility graphs and graph models in wireless sensor network problems such as topology control, fault tolerance, and clustering.

The content is presented in a simple and straightforward manner with ample illustrations using neat and apt diagrams (graphs). The book is definitely good for students learning graph theory at the undergraduate and postgraduate levels.

Reviewer:  Sudev Naduvath Review #: CR145757 (1803-0127)
Bookmark and Share
  Reviewer Selected
 
 
Graph Theory (G.2.2 )
 
 
Reference (A.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy