An Introduction to Graph Theory (First Edition) S Pirzada

In this comprehensive and up-to-date book on graph theory, the reader is provided a thorough understanding of the fundamentals of the subject - the structure of graphs, the techniques used to analyse problems in graph theory, and the use of graph-theoretical algorithms in mathematics, engineering and computer science. Many topics, not generally found in standard books, are described here. These include new proofs of various classical theorems, signed degree sequences, criteria for graphical sequences, eccentric sequences, matching and decomposition of planar graphs into trees, and scores in digraphs.



Table of Contents

1. Introduction 
1.1 Basic Concepts
1.2 Degrees
1.3 Isomorphism
1.4 Types of Graphs
1.5 Graph Properties
1.6 Paths, Cycles and Components
1.7 Operations on Graphs
1.8 Topological Operations
1.9 Distance and Eccentricity
1.10 Exercises

2. Degree Sequences 
2.1 Degree Sequences
2.2 Criteria for Degree Sequences
2.3 Degree Set of a Graph
2.4 New Criterion
2.5 Equivalence of Seven Criteria
2.6 Signed Graphs
2.7 Exercises

3. Eulerian and Hamiltonian Graphs 
3.1 Euler Graphs
3.2 Konigsberg Bridge Problem
3.3 Unicursal Graphs
iv Contents
3.4 Arbitrarily Traceable Graphs
3.5 Sub-Eulerian Graphs
3.6 Hamiltonian Graphs
3.7 Pancyclic Graphs
3.8 Exercises

4. Trees 
4.1 Basics
4.2 Rooted and Binary Trees
4.3 Number of Labelled Trees
4.4 The Fundamental Cycles
4.5 Generation of Trees
4.6 Helly Property
4.7 Signed Trees
4.8 Exercises

5. Connectivity 
5.1 Basic Concepts
5.2 Block-Cut Vertex Tree
5.3 Connectivity Parameters
5.4 Menger’s Theorem
5.5 Some Properties of a Bond
5.6 Fundamental Bonds
5.7 Block Graphs and Cut Vertex Graphs
5.8 Exercises

6. Planarity 
6.1 Kuratowski’s two graphs
6.2 Region
6.3 Euler’s Theorem
6.4 Kuratowski’s theorem
6.5 Geometric Dual
6.6 Polyhedron
6.7 Decomposition of Some Planar Graphs
6.8 Exercises

7. Colourings 
7.1 Vertex Colouring
7.2 Critical Graphs
7.3 Brooks Theorem
7.4 Edge Colouring
7.5 Region Colouring (Map Coloring)
7.6 Heawood Map-Colouring Theorem
7.7 Uniquely Colourable Graphs
7.8 Hajos Conjecture
7.9 Exercises

8. Matchings and Factors 
8.1 Matchings
8.2 Factors
8.3 Antifactor Sets
8.4 The f -factor Theorem
8.5 Degree Factors
8.6 (g, f ) and [a, b]-factors
8.7 Exercises

9. Edge Graphs and Eccentricity Sequences 
9.1 Edge Graphs
9.2 Edge Graphs and Traversability
9.3 Total Graphs
9.4 Eccentricity Sequences and Sets
9.5 Distance Degree Regular and Distance Regular Graphs
9.6 Isometry
9.7 Exercises

10. Graph Matrices 
10.1 Incidence Matrix
10.2 Submatrices of A(G)
10.3 Cycle Matrix
10.4 Cut-Set Matrix
10.5 Fundamental Cut Set Matrix
10.6 Relations between Af , Bf and Cf
10.7 Path Matrix
10.8 Adjacency Matrix
10.9 Exercises

11. Digraphs 
11.1 Basic Definitions
11.2 Digraphs and Binary Relations
11.3 Directed Paths and Connectedness
11.4 Euler Digraphs
11.5 Hamiltonian Digraphs
11.6 Trees with Directed Edges
11.7 Matrices A, B and C of Digraphs
11.8 Number of Arborescences
11.9 Tournaments
11.10 Exercises

12. Score Structure in Digraphs 
12.1 Score Sequences in Tournaments
12.2 Frequency Sets in Tournaments
12.3 Score Sets in Tournaments
12.4 Lexicographic Enumeration and Tournament Construction
12.5 Simple Score Sequences in Tournaments
12.6 Score Sequences of Self-Converse Tournaments
12.7 Score Sequences of Bipartite Tournaments
12.8 Uniquely Realisable (simple) Pairs of Score Sequences
12.9 Score Sequences of Oriented Graphs
12.10 Score Sets in Oriented Graphs
12.11 Uniquely Realisable (simple) Score Sequences in Oriented Graphs
12.12 Score Sequences in Oriented Bipartite Graphs
12.13 Score Sequences of Semi Complete Digraphs
12.14 Exercises

References
Index

About the Author

S Pirzada is a professor of mathematics at the University of Kashmier. He obtained his PhD in Applied Mathematics from Aligarh Muslim University in 1995. He has taught at the National Institute of Technology, Srinagar, University of Kashmir, and the King Fahn University of Petroleum and Minerals, Saudi Arabia. He is a recipient of the DST (J&K) Young Scientist award. He has made contributions in the areas of directed graphs, signed graphs and hypergraphs. He has published several research papers in various international journals and is the co-author of the book Analytical Solid Geometry.