The textbook “Introduction to Graph Theory” has been designed primarily to meet the requirements of B.E./B.Tech students of all technical colleges affiliated to U.P. Technical University. The book will also be fruitful to the candidates appearing in UGC, NET, GATE and other competitive examinations. All the principles and fundamental concepts have been explained very clearly leaving no scope of illusion and confusion. The language used in this book is simple and lucid in style. No previous knowledge of Graph Theory is required to follow this book. The book has been made as much self-contained as could be possible. Many people have contributed directly or indirectly to the completion of this book. We gratefully acknowledge our indebtedness to various authors and publishers whose books have been freely consulted during the preparation of this book. We specially thank to Mrs. Veena Mathur, Er. Navin P. Mathur, Dr. Manish Sharma, Dr. Ravinder Sing and Dr. Neeraj Saxena , who always encouraged us and gave us constructive suggestions. We are thankful to all of them. We wish to thank our colleagues of the departments of Mathematics and Computer Science for their many helpful corrections, comments and suggestions. Any suggestions for improving the contents would be warmly appreciated.
Additional Info
  • Publisher: Laxmi Publications
  • Language: English
  • ISBN : 978-81-318-0774-3
  • Chapter 1

    ELEMENTARY COMBINATORICS Price 2.99  |  2.99 Rewards Points

    In our daily life, we often come across the problems of finding the number of ways in which a set of objects may be arranged or selected under certain given condition or conditions. This process is also known as the sophisticated counting or counting without counting.
  • Chapter 2


    We bring back to memory that a function is a binary relation that assigns to each element in the domain, a unique value which is an element in the range.
  • Chapter 3

    RECURRENCE RELATIONS Price 2.99  |  2.99 Rewards Points

    The expressions for permutations and combinations are the most fundamental tools for counting the elements of finite sets. These expressions often prove inadequate for many combinatorial problems that the computer scientist must face. An important alternate approach uses recurrence relations (sometimes called difference equations) to define the terms of a sequence. A sequence is a function whose domain is some infinite set of integers (often N) and whose range is a set of real numbers
  • Chapter 4

    GRAPHS Price 2.99  |  2.99 Rewards Points

    Many real world situations can be described by using diagrams consisting of a set of points with lines joining certain pairs of these points. For examples the points could represent communication centres, with line representing communication links. In such diagrams one is mainly interested in whether or not two given points are joined by a line. A mathematical abstraction of this type gives rise to the concept of a graph.
  • Chapter 5

    EULER AND HAMILTONIAN GRAPHS Price 2.99  |  2.99 Rewards Points

    If some closed walk in a graph contains all the edges of the graph, then the walk is called an Euler line and the graph an Euler graph. A path in a graph G is called Euler path if it includes every edges excatly once. Since the path contains every edge exactly once, it is also called Euler tail. An Euler path that is a circuit is called Euler circuit. So, a graph which has a Eulerian circuit is called an Eulerian graph.
  • Chapter 6

    TREES Price 2.99  |  2.99 Rewards Points

    Tree is a special type of relation that is useful in a variety of computer science application and is usually represented by its digraph. These relations are essential for the construction of databases and language compilers. Trees are the most important graphs in graph theory. Many of the ‘applications of graph theory, directly or indirectly, involves trees. Trees are useful for describing any structure which involves hierarchy.
  • Chapter 7

    CUT - SETS AND NETWORK FLOWS Price 2.99  |  2.99 Rewards Points

    A cut-set in a connected graph G, is a set of edges whose removal from G leaves G disconnected. Suppose G is a connected graph having the edge set
  • Chapter 8

    PLANAR AND DUAL GRAPHS Price 2.99  |  2.99 Rewards Points

    We introduced this topic through an activity. A famous problem is that of connecting each of three houses, as shown in figure 8.1, to all three services (electricity, gas and water) with no pipe/cable crossing another. Four of the nine lines needed have already been put into the figure.
  • Chapter 9

    VECTOR SPACES OF A GRAPH Price 2.99  |  2.99 Rewards Points

    In the theory as well as in the applications of graphs, modern abstract algebra plays a very important role. It is very essential and powerful tool for those wishing to do research in the field of the graph theory Digital computers do not work on pictorial graphs. So it is necessary to represent and manipulate graphs algebraically for solving graph problems. Before understanding the basic definition of vector and vector spaces associated with a graph. We have to go through some definitions. because these concepts form the body for vector spaces.
  • Chapter 10

    MATRIX - REPRESENTATION OF GRAPHS Price 2.99  |  2.99 Rewards Points

    Although a diagrammatic representation of a graph is very convenient for a visual study but this is only possible when the number of nodes and edges is reasonably small. Matrix representation is better for computer processing because matrix is a convenient and useful way of representing a graph to a computer. The advantages of representing the graph in matrix form lies on the fact that many results of matrix algebra can be applied to study the structural properties of graphs from an algebraic point of view. In many applications of graph theory, such as in electrical network analysis and operations research, matrices proved to be the most powerful tools in expressing the problem. There are number of matrices which one can associate with any graph.
  • Chapter 11

    COLORING OF GRAPHS Price 2.99  |  2.99 Rewards Points

    Simple decision making problems such as scheduling of committee meeting times without overlapping, waiting line problems, scheduling n jobs on m different machines etc., may also be represented by graphs and solved by coloring. In this chapter, we will introduce the idea of coloring in graphs.
  • Chapter 12

    DIRECTED GRAPHS Price 2.99  |  2.99 Rewards Points

    Although many problems lend themselves naturally to a graph theoretic formulation, the concept of a graph is sometimes not quite adequate when dealing with problems of traffic flow, for example, it is necessary to know which roads in the network are one-way and in which direction traffic is permitted. Similarly many physical situations require directed graphs, the graphs in which edges have directions.
  • Chapter 13

    ENUMERATION OF GRAPHS Price 2.99  |  2.99 Rewards Points

    All graph-enumeration problems can be divided into two categories : (i) Counting the number of different graphs or directed graphs of a particular kind for example all connected graphs with 6 vertices and 2 cycles. (ii) Counting the number of subgraphs of a particular type in a given graph G. For example, the number of edge disjoint paths of length k between vertices v1 and v2. In type (i) the word “different” is of utmost importance and must be clearly understood. If the graphs are labeled i.e., each vertex is assigned a name distinct from all others, all graphs are counted.
  • Chapter 14

    APPLICATIONS OF GRAPH THEORY Price 2.99  |  2.99 Rewards Points

    Graph theory is playing an increasingly important role in the design, analysis, and testing of computer programs. Its importance is derived from the fact that flow of control and flow of data for any program can be expressed in terms of directed graphs. From the graph representing the flow of control, called the program graph, many others can be derived that either partially or completely preserve the program control structure. One derived graph known as a cyclomatic tree is of particular value in program testing. It is so named because the number of leaves of the tree is equal to the cyclomatic number of the program graph.

About the Author