Author | Bollobรกs, Bรฉla. author |
---|---|
Title | Modern Graph Theory [electronic resource] / by Bรฉla Bollobรกs |
Imprint | New York, NY : Springer New York : Imprint: Springer, 1998 |
Connect to | http://dx.doi.org/10.1007/978-1-4612-0619-4 |
Descript | XIV, 394 p. 3 illus. online resource |
I Fundamentals -- I.1 Definitions -- I.2 Paths, Cycles, and Trees -- I.3 Hamilton Cycles and Euler Circuits -- I.4 Planar Graphs -- I.5 An Application of Euler Trails to Algebra -- I.6 Exercises -- II Electrical Networks -- II.1 Graphs and Electrical Networks -- II.2 Squaring the Square -- II.3 Vector Spaces and Matrices Associated with Graphs -- II.4 Exercises -- II.5 Notes -- III Flows, Connectivity and Matching -- III.1 Flows in Directed Graphs -- III.2 Connectivity and Mengerโs Theorem -- III.3 Matching -- III.4 Tutteโs 1-Factor Theorem -- III.5 Stable Matchings -- III.6 Exercises -- III.7 Notes -- IV Extremal Problems -- IV.1 Paths and Cycles -- IV.2 Complete Subgraphs -- IV.3 Hamilton Paths and Cycles -- W.4 The Structure of Graphs -- IV 5 Szemerรฉdiโs Regularity Lemma -- IV 6 Simple Applications of Szemerรฉdiโs Lemma -- IV.7 Exercises -- IV.8 Notes -- V Colouring -- V.1 Vertex Colouring -- V.2 Edge Colouring -- V.3 Graphs on Surfaces -- V.4 List Colouring -- V.5 Perfect Graphs -- V.6 Exercises -- V.7 Notes -- VI Ramsey Theory -- VI.1 The Fundamental Ramsey Theorems -- VI.2 Canonical Ramsey Theorems -- VI.3 Ramsey Theory For Graphs -- VI.4 Ramsey Theory for Integers -- VI.5 Subsequences -- VI.6 Exercises -- VI.7 Notes -- VII Random Graphs -- VII.1 The Basic Models-The Use of the Expectation -- VII.2 Simple Properties of Almost All Graphs -- VII.3 Almost Determined Variables-The Use of the Variance -- VII.4 Hamilton Cycles-The Use of Graph Theoretic Tools -- VII.5 The Phase Transition -- VII.6 Exercises -- VII.7 Notes -- VIII Graphs, Groups and Matrices -- VIII.1 Cayley and Schreier Diagrams -- VIII.2 The Adjacency Matrix and the Laplacian -- VIII.3 Strongly Regular Graphs -- VIII.4 Enumeration and Pรณlyaโs Theorem -- VIII.5 Exercises -- IX Random Walks on Graphs -- IX.1 Electrical Networks Revisited -- IX.2 Electrical Networks and Random Walks -- IX.3 Hitting Times and Commute Times -- IX.4 Conductance and Rapid Mixing -- IX.5 Exercises -- IX.6 Notes -- X The Tutte Polynomial -- X.1 Basic Properties of the Tutte Polynomial -- X.2 The Universal Form of the Tutte Polynomial -- X.3 The Tutte Polynomial in Statistical Mechanics -- X.4 Special Values of the Tutte Polynomial -- X.5 A Spanning Tree Expansion of the Tutte Polynomial -- X.6 Polynomials of Knots and Links -- X.7 Exercises -- X.8 Notes -- Symbol Index -- Name Index