Details

<p>Foreword  ix</p> <p>Introduction xi</p> <p><b>Chapter 1. A First Encounter with Graphs  1</b></p> <p>1.1. A few definitions  1</p> <p>1.1.1. Directed graphs  1</p> <p>1.1.2. Unoriented graphs 9</p> <p>1.2. Paths and connected components  14</p> <p>1.2.1. Connected components  16</p> <p>1.2.2. Stronger notions of connectivity 18</p> <p>1.3. Eulerian graphs  23</p> <p>1.4. Defining Hamiltonian graphs 25</p> <p>1.5. Distance and shortest path  27</p> <p>1.6. A few applications 30</p> <p>1.7. Comments 35</p> <p>1.8. Exercises  37</p> <p><b>Chapter 2. A Glimpse at Complexity Theory 43</b></p> <p>2.1. Some complexity classes 43</p> <p>2.2. Polynomial reductions 46</p> <p>2.3. More hard problems in graph theory 49</p> <p><b>Chapter 3. Hamiltonian Graphs 53</b></p> <p>3.1. A necessary condition 53</p> <p>3.2. A theorem of Dirac  55</p> <p>3.3. A theorem of Ore and the closure of a graph  56</p> <p>3.4. Chvátal’s condition on degrees  59</p> <p>3.5. Partition of Kn into Hamiltonian circuits  62</p> <p>3.6. De Bruijn graphs and magic tricks  65</p> <p>3.7. Exercises  68</p> <p><b>Chapter 4. Topological Sort and Graph Traversals  69</b></p> <p>4.1. Trees  69</p> <p>4.2. Acyclic graphs 79</p> <p>4.3. Exercises  82</p> <p><b>Chapter 5. Building New Graphs from Old Ones  85</b></p> <p>5.1. Some natural transformations  85</p> <p>5.2. Products  90</p> <p>5.3. Quotients  92</p> <p>5.4. Counting spanning trees  93</p> <p>5.5. Unraveling 94</p> <p>5.6. Exercises  96</p> <p><b>Chapter 6. Planar Graphs 99</b></p> <p>6.1. Formal definitions 99</p> <p>6.2. Euler’s formula 104</p> <p>6.3. Steinitz’ theorem  109</p> <p>6.4. About the four-color theorem 113</p> <p>6.5. The five-color theorem  115</p> <p>6.6. From Kuratowski’s theorem to minors  120</p> <p>6.7. Exercises  123</p> <p><b>Chapter 7. Colorings  127</b></p> <p>7.1. Homomorphisms of graphs  127</p> <p>7.2. A digression: isomorphisms and labeled vertices  131</p> <p>7.3. Link with colorings  134</p> <p>7.4. Chromatic number and chromatic polynomial 136</p> <p>7.5. Ramsey numbers  140</p> <p>7.6. Exercises  147</p> <p><b>Chapter 8. Algebraic Graph Theory  151</b></p> <p>8.1. Prerequisites  151</p> <p>8.2. Adjacency matrix 154</p> <p>8.3. Playing with linear recurrences  160</p> <p>8.4. Interpretation of the coefficients 168</p> <p>8.5. A theorem of Hoffman  169</p> <p>8.6. Counting directed spanning trees 172</p> <p>8.7. Comments 177</p> <p>8.8. Exercises  178</p> <p><b>Chapter 9. Perron–Frobenius Theory 183</b></p> <p>9.1. Primitive graphs and Perron’s theorem 183</p> <p>9.2. Irreducible graphs 188</p> <p>9.3. Applications  190</p> <p>9.4. Asymptotic properties 195</p> <p>9.4.1. Canonical form  196</p> <p>9.4.2. Graphs with primitive components 197</p> <p>9.4.3. Structure of connected graphs 206</p> <p>9.4.4. Period and the Perron–Frobenius theorem 214</p> <p>9.4.5. Concluding examples 218</p> <p>9.5. The case of polynomial growth  224</p> <p>9.6. Exercises  231</p> <p><b>Chapter 10. Google’s Page Rank  233</b></p> <p>10.1. Defining the Google matrix 238</p> <p>10.2. Harvesting the primitivity of the Google matrix  241</p> <p>10.3. Computation 246</p> <p>10.4. Probabilistic interpretation 246</p> <p>10.5. Dependence on the parameter α  247</p> <p>10.6. Comments 248</p> <p>Bibliography 249</p> <p>Index  263</p>

<p><strong>Michel RIGO</strong>, Full professor, University of Liège, Department of Math., Belgium.

US