Graph Theory and Combinatorics

The book is divided into eight chapters. Chapters 1-4 deal with Graph Theory and Chapters 5-8 deal with Combinatorics. The topics covered are: Directed graphs, graphs, planar graphs, graph colouring, trees, optimization and matching, principles of counting, generating functions, and recurrence relations.

The book is designed as a self-contained, comprehensive study material. Each topic is treated in systematic and logical manner. A large number of Worked Examples and graded Exercises with answers form an integral part of the text material.

In this edition, some sections have been rewritten and several new worked examples and exercises have been incorporated.

PART A : GRAPH THEORY

Chapter 1. Directed Graphs and Graphs

  • 1.1 Directed Graphs
  • 1.2 Graphs
  • 1.2.1 Vertex degree and Handshaking property
  • 1.3 Isomorphism
  • 1.4 Subgraphs
  • 1.5 Operations on Graphs
  • 1.6 Walks and their classifification
  • 1.7 Connected and Disconnected Graphs
  • 1.8 Euler circuits and Euler trails
  • 1.9 The K¨onigsberg Bridge Problem
  • 1.10 Hamilton cycles and Hamilton paths

Chapter 2. Planar Graphs and Colouring

  • 2.1 Planar and non-planar graphs
  • 2.2 Euler's formula
  • 2.3 Detection of planarity
  • 2.4 Dual of a planar graph
  • 2.5 Graph Colouring
  • 2.5.1 Chromatic Polynomials
  • 2.6 Map Colouring

Chapter 3. Trees

  • 3.1 Trees and their Basic properties
  • 3.2 Rooted Trees
  • 3.2.1 Preorder and Postorder Traversals
  • 3.2.2 Sorting
  • 3.3 Spanning Trees
  • 3.3.1 Depth-First Search and Breadth-First Search
  • 3.4 Prefifix codes and Weighted trees

Chapter 4. Optimization and Matching

  • 4.1 Minimal Spanning Tree
  • 4.2 Cut-sets; Edge connectivity; Vertex connectivity
  • 4.3 Network Flows
  • 4.3.1 Max-flflow and Min-cut Theorem
  • 4.4 Shortest Path
  • 4.5 Matchings

PART B : COMBINATORICS

Chapter 5. Principles of Counting - I

  • 5.1 The Rules of Sum and Product
  • 5.2 Permutations
  • 5.3 Combinations
  • 5.3.1 Binomial and Multinomial Theorems
  • 5.3.2 Combinations with Repetitions
  • 5.4 Catalan Numbers
  • Chapter 6. Principles of Counting - II
  • 309–362
  • 6.1 The Principle of Inclusion-Exclusion
  • 6.2 Derangements
  • 6.3 Rook Polynomials

Chapter 7. Generating Functions

  • 7.1 Ordinary generating function
  • 7.1.1 Convolution of Sequences
  • 7.1.2 A Counting Technique
  • 7.1.3 Partitions of Integers
  • 7.2 Exponential generating function

Chapter 8. Recurrence Relations

  • 8.1 First-order Recurrence Relations
  • 8.2 Second-order Homogeneous Recurrence Relations
  • 8.3 Third and higher-order Linear Homogeneous Recurrence Relations
  • 8.4 Nonhomogenous Recurrence Relations of second and higher orders
  • 8.5 Method of Generating Functions
  • 8.5.1 Method of generating functions for First-order Recurrence Relations
  • 8.5.2 Method of generating functions for Second-order Recurrence Relations


Syllabus
Index