Skip to main content
main-content
Top

About this book

This undergraduate textbook provides an introduction to graph theory, which has numerous applications in modeling problems in science and technology, and has become a vital component to computer science, computer science and engineering, and mathematics curricula of universities all over the world.

The author follows a methodical and easy to understand approach. Beginning with the historical background, motivation and applications of graph theory, the author first explains basic graph theoretic terminologies. From this firm foundation, the author goes on to present paths, cycles, connectivity, trees, matchings, coverings, planar graphs, graph coloring and digraphs as well as some special classes of graphs together with some research topics for advanced study.

Filled with exercises and illustrations, Basic Graph Theory is a valuable resource for any undergraduate student to understand and gain confidence in graph theory and its applications to scientific research, algorithms and problem solving.

Table of Contents

Chapter 1. Graphs and Their Applications

Abstract
A graph consists of a set of vertices and set of edges, each joining two vertices. Usually an object can be represented by a vertex and a relationship between two objects is represented by an edge. In this chapter we go through some applications of graphs in solving real-world problems.
Md. Saidur Rahman

Chapter 2. Basic Graph Terminologies

Abstract
In this chapter, we learn some definitions of basic graph theoretic terminologies and know some preliminary results of graph theory.
Md. Saidur Rahman

Chapter 3. Paths, Cycles, and Connectivity

Abstract
In this chapter, we study some important fundamental concepts of graph theory. In Section 3.1 we start with the definitions of walks, trails, paths, and cycles. The well-known Eulerian graphs and Hamiltonian graphs are studied in Sections 3.2 and 3.3, respectively. In Section 3.4, we study the concepts of connectivity and connectivity-driven graph decompositions.
Md. Saidur Rahman

Chapter 4. Trees

Abstract
A tree is a connected graph that contains no cycle. In this chapter we know some properties of trees which are useful for solving computational problems on trees.
Md. Saidur Rahman

Chapter 5. Matching and Covering

Abstract
In this chapter we study matchings, vertex cover, independent set, dominating set and factor of a graph with their real-world applications.
Md. Saidur Rahman

Chapter 6. Planar Graphs

Abstract
A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. In this chapter we study planar graphs.
Md. Saidur Rahman

Chapter 7. Graph Coloring

Abstract
Probably graph coloring concept naturally arose from its application in map coloring: given a map containing several countries, we wish to color the countries in the map in such a way that neighboring countries receive different colors to make the countries distinct. In this chapter we know about vertex coloring, edge coloring, chromatic number, chromatic index, chromatic polynomial, etc.
Md. Saidur Rahman

Chapter 8. Digraphs

Abstract
A graph is usually called a directed graph or a digraph if its edges have directions. The concept of directed graphs has many applications in solving real-world problems. In this chapter we study some properties of digraphs.
Md. Saidur Rahman

Chapter 9. Special Classes of Graphs

Abstract
In this chapter, we know about some special classes of graphs. Special classes of graphs play important roles in graph algorithmic studies. When we find a computationally hard problem for general graphs, we try to solve those problems for special classes of graphs.
Md. Saidur Rahman

Chapter 10. Some Research Topics

Abstract
In this chapter, we introduce some research areas where the students learning graph theory may find interest. Since graphs have applications in modeling many real-world problems, a researcher in graph theory can work on fundamental properties of graphs as well as developing graph models for practical applications and on devising efficient algorithms.
Md. Saidur Rahman
Additional information