Advanced Graph Theory and Combinatorics

Advanced Graph Theory focuses on some of the main notions arising in graph theory with an emphasis from the very start of the book on the possible applications of the theory and the fruitful links existing with linear algebra. The second part of the book covers basic material related to linear recurrence relations with application to counting and the asymptotic estimate of the rate of growth of a sequence satisfying a recurrence relation.

Advanced Graph Theory focuses on some of the main notions arising in graph theory with an emphasis from the very start of the book on the possible applications of the theory and the fruitful links existing with linear algebra. The second part of the book covers basic material related to linear recurrence relations with application to counting and the asymptotic estimate of the rate of growth of a sequence satisfying a recurrence relation.

Foreword ixIntroduction xiChapter 1. A First Encounter with Graphs 11.1. A few definitions 11.1.1. Directed graphs 11.1.2. Unoriented graphs 91.2. Paths and connected components 141.2.1. Connected components 161.2.2. Stronger notions of connectivity 181.3. Eulerian graphs 231.4. Defining Hamiltonian graphs 251.5. Distance and shortest path 271.6. A few applications 301.7. Comments 351.8. Exercises 37Chapter 2. A Glimpse at Complexity Theory 432.1. Some complexity classes 432.2. Polynomial reductions 462.3. More hard problems in graph theory 49Chapter 3. Hamiltonian Graphs 533.1. A necessary condition 533.2. A theorem of Dirac 553.3. A theorem of Ore and the closure of a graph 563.4. Chvátal's condition on degrees 593.5. Partition of Kn into Hamiltonian circuits 623.6. De Bruijn graphs and magic tricks 653.7. Exercises 68Chapter 4. Topological Sort and Graph Traversals 694.1. Trees 694.2. Acyclic graphs 794.3. Exercises 82Chapter 5. Building New Graphs from Old Ones 855.1. Some natural transformations 855.2. Products 905.3. Quotients 925.4. Counting spanning trees 935.5. Unraveling 945.6. Exercises 96Chapter 6. Planar Graphs 996.1. Formal definitions 996.2. Euler's formula 1046.3. Steinitz' theorem 1096.4. About the four-color theorem 1136.5. The five-color theorem 1156.6. From Kuratowski's theorem to minors 1206.7. Exercises 123Chapter 7. Colorings 1277.1. Homomorphisms of graphs 1277.2. A digression: isomorphisms and labeled vertices 1317.3. Link with colorings 1347.4. Chromatic number and chromatic polynomial 1367.5. Ramsey numbers 1407.6. Exercises 147Chapter 8. Algebraic Graph Theory 1518.1. Prerequisites 1518.2. Adjacency matrix 1548.3. Playing with linear recurrences 1608.4. Interpretation of the coefficients 1688.5. A theorem of Hoffman 1698.6. Counting directed spanning trees 1728.7. Comments 1778.8. Exercises 178Chapter 9. Perron-Frobenius Theory 1839.1. Primitive graphs and Perron's theorem 1839.2. Irreducible graphs 1889.3. Applications 1909.4. Asymptotic properties 1959.4.1. Canonical form 1969.4.2. Graphs with primitive components 1979.4.3. Structure of connected graphs 2069.4.4. Period and the Perron-Frobenius theorem 2149.4.5. Concluding examples 2189.5. The case of polynomial growth 2249.6. Exercises 231Chapter 10. Google's Page Rank 23310.1. Defining the Google matrix 23810.2. Harvesting the primitivity of the Google matrix 24110.3. Computation 24610.4. Probabilistic interpretation 24610.5. Dependence on the parameter alpha 24710.6. Comments 248Bibliography 249Index 263