The concept of a graph is fundamental in mathematics since it conveniently encodes diverse relations and facilitates combinatorial analysis of many complicated counting problems. In this book, the authors have traced the origins of graph theory from its humble beginnings of recreational mathematics to its modern setting for modeling communication networks as is evidenced by the World Wide Web graph used by many Internet search engines. This book is an introduction to graph theory and combinatorial analysis. It is based on courses given by the second author at Queen's University at Kingston, Ontario, Canada between 2002 and 2008. The courses were aimed at students in their final year of their undergraduate program.
Errate: http://www.math.udel.edu/~cioaba/book_errata.pdf
Author(s): Sebastian M. Cioaba, M. Ram Murty
Series: Hindustan Book Agency
Publisher: Amer Mathematical Society
Year: 2009
Language: English
Pages: 186
Tags: Combinatorics;Pure Mathematics;Mathematics;Science & Math;Mathematics;Algebra & Trigonometry;Calculus;Geometry;Statistics;Science & Mathematics;New, Used & Rental Textbooks;Specialty Boutique
Contents
Chapter 1. Basic Notions of Graph Theory 1
1.1. The Königsberg Bridges Problem 1
1.2. What is a Graph? 2
1.3. Mathematical Induction and Graph Theory Proofs 4
1.4. Eulerian Graphs 6
1.5. Bipartite Graphs 7
1.6. Exercises 8
Chapter 2. Recurrence Relations 10
2.1. Binomial Coefficients 10
2.2. Derangements 13
2.3. Involutions 15
2.4. Fibonacci Numbers 16
2.5. Catalan Numbers 17
2.6. Bell Numbers 20
2.7. Exercises 21
Chapter 3. The Principle of Inclusion and Exclusion 24
3.1. The Main Theorem 24
3.2. Derangements Revisited 25
3.3. Counting Surjective Maps 25
3.4. Stirling Numbers of the First Kind 26
3.5. Stirling Numbers of the Second Kind 27
3.6. Exercises 30
Chapter 4. Matrices and Graphs 33
4.1. Adjacency and Incidence Matrices 33
4.2. Graph Isomorphism 34
4.3. Bipartite Graphs and Matrices 36
4.4. Diameter and Eigenvalues 37
4.5. Exercises 38
Chapter 5. Trees 41
5.1. Forests, Trees and Leaves 41
5.2. Counting Labeled Trees 42
5.3. Spanning Subgraphs 44
5.4. Minimllm Spanning Trees and Kruskal's Algorithm 47
5.5. Exercises 49
Chapter 6. Mobius Inversion and Graph Colouring 52
6.1. Posets and Mobius Functions 52
6.2. Lattices 54
6.3. The Classical Mobius Function 56
6.4. The Lattice of Partitions 57
6.5. Colouring Graphs 59
6.6. Colouring Trees and Cycles 62
6.7. Sharper Bounds for the Chromatic Number 64
6.8. Sudoku Puzzles and Chromatic Polynomials 66
6.9. Exercises 69
Chapter 7. Enumeration under Group Action 72
7.1. The Orbit-Stabilizer Formula 72
7.2. Burnside's Lemma 76
7.3. P6lya Theory 78
7.4. Exercises 84
Chapter 8. Matching Theory 86
8.1. The Marriage Theorem 86
8.2. Systems of Distinct Representatives 88
8.3. Systems of Common Representatives 89
8.4. Doubly Stochastic Matrices 90
8.5. Weighted Bipartite Matching 91
8.6. Matchings in General Graphs 94
8.7. Connectivity 95
8.8. Exercises 97
Chapter 9. Block Designs 100
9.1. Gaussian Binomial Coefficients 100
9.2. Introduction to Designs 103
9.3. Incidence Matrices 105
9.4. Examples of Designs 108
9.5. Proof of the Bruck-Ryser-Chowla Theorem 110
9.6. Codes and Designs 113
9.7. Exercises 115
Chapter 10. Planar Graphs 118
10.1. Euler's Formula 118
10.2. The Five Colour Theorem 121
10.3. Colouring Maps on Surfaces of Higher Genus 123
10.4. Exercises 125
Chapter 11. Edges and Cycles 127
11.1. Edge Colourings 127
11.2. Hamiltonian Cycles 130
11.3. Ramsey Theory 134
11.4. Exercises 139
Chapter 12. Regular Graphs 141
12.1. Eigenvalues of Regular Graphs 141
12.2. Diameter of Regular Graphs 142
12.3. Ramanujan Graphs 148
12.4. Basic Facts about Groups and Characters 148
12.5. Cayley Graphs 151
12.6. Expanders 154
12.7. Counting Paths in Regular Graphs 156
12.8. The Ihara Zeta Function of a Graph 157
12.9. Exercises 158
Chapter 13. Hints 160
Bibliography 169
Index 170
