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

Description

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. 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