2017 | Book

# Basic Graph Theory

Author: Md. Saidur Rahman

Publisher:

Book Series : Undergraduate Topics in Computer Science

Part of:

insite
SEARCH

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.

##### 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
##### Backmatter
Title
Basic Graph Theory
Author
Md. Saidur Rahman