A First Course in Graph Theory and Combinatorics: Second Edition (Texts and Readings in Mathematics, 55)

✍ Scribed by Sebastian M. Cioabă, M. Ram Murty

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 231
• Edition: 1st ed. 2022
• Category: Library

✦ Synopsis

This book discusses the origin of graph theory from its humble beginnings in recreational mathematics to its modern setting or modeling communication networks, as is evidenced by the World Wide Web graph used by many Internet search engines. The second edition of the book includes recent developments in the theory of signed adjacency matrices involving the proof of sensitivity conjecture and the theory of Ramanujan graphs. In addition, the book discusses topics such as Pick’s theorem on areas of lattice polygons and Graham–Pollak’s work on addressing of graphs. The concept of graph is fundamental in mathematics and engineering, as it conveniently encodes diverse relations and facilitates combinatorial analysis of many theoretical and practical problems. The text is ideal for a one-semester course at the advanced undergraduate level or beginning graduate level.

✦ Table of Contents

Preface to Second Edition
Preface to First Edition
Contents
About the Authors
1 Basic Graph Theory
1.1 Königsberg Bridges Problem
1.2 What Is a Graph?
1.3 Mathematical Induction
1.4 Eulerian Graphs
1.5 Bipartite Graphs
1.6 Exercises
Exercises
2 Basic Counting
2.1 Finite Sets and Permutations
2.2 Fibonacci Numbers
2.3 Catalan Numbers
2.4 Derangements and Involutions
2.5 Bell Numbers
2.6 Exercises
Exercises
References
3 The Principle of Inclusion and Exclusion
3.1 The Main Theorem
3.2 Derangements Revisited
3.3 Counting Surjective Maps
3.4 Stirling Numbers of the First Kind
3.5 Stirling Numbers of the Second Kind
3.6 Exercises
Exercises
4 Graphs and Matrices
4.1 Adjacency Matrix
4.2 Graph Isomorphisms
4.3 Bipartite Graphs and Eigenvalues
4.4 Diameters and Eigenvalues
4.5 Incidence Matrices and the Laplacian Matrix
4.6 Exercises
Exercises
5 Trees
5.1 Forests, Trees, and Leaves
5.2 Labelled Trees
5.3 Spanning Trees
5.4 MST, BFS, and DFS
5.5 Lagrange's Inversion Formula
5.6 Exercises
Exercises
Reference
6 Möbius Inversion and Graph Colouring
6.1 Posets and Möbius Functions
6.2 Applications of Möbius Inversion
6.3 The Chromatic Polynomial
6.4 The Chromatic Number
6.5 Sudoku Puzzles
6.6 Exercises
Exercises
Reference
7 Enumeration Under Group Action
7.1 Basic Facts About Groups
7.2 The Orbit-Stabilizer Formula
7.3 Burnside's Lemma
7.4 Sylow Theorems
7.5 Pólya Theory
7.6 Exercises
Exercises
References
8 Matching Theory
8.1 The Marriage Theorem
8.2 Latin Squares
8.3 Doubly Stochastic Matrices
8.4 Weighted Bipartite Matching
8.5 Matchings and Connectivity
8.6 Exercises
Exercises
References
9 Block Designs
9.1 Gaussian Binomial Coefficients
9.2 Design Theory
9.3 Incidence Matrices
9.4 Bruck-Ryser-Chowla Theorem
9.5 Codes and Designs
9.6 Exercises
Exercises
Reference
10 Planar Graphs
10.1 Euler's Formula
10.2 The Platonic Solids
10.3 The Five Colour Theorem
10.4 Colouring Graphs on Surfaces
10.5 Pick's Theorem
10.6 Exercises
Exercises
References
11 Edges and Cycles
11.1 Edge Colourings
11.2 Hamiltonian Cycles
11.3 Turán's Theorem
11.4 Ramsey Theory
11.5 Graham-Pollak Theorem
11.6 Exercises
Exercises
References
12 Expanders and Ramanujan Graphs
12.1 Eigenvalues and Expanders
12.2 The Alon-Boppana Theorem
12.3 Group Characters and Cayley Graphs
12.4 The Ihara Zeta Function of a Graph
12.5 Ramanujan Graphs
12.6 Exercises
References
13 Hints
Appendix Index
Index