# A Textbook of Graph Theory

Springer Science & Business Media, 2000 - Mathematics - 227 pages
Graph theory has experienced a tremendous growth during the 20th century. One of the main reasons for this phenomenon is the applicability of graph theory in other disciplines such as physics, chemistry, psychology, sociology, and theoretical computer science. This book aims to provide a solid background in the basic topics of graph theory. It covers Dirac's theorem on k-connected graphs, Harary-Nashwilliam's theorem on the hamiltonicity of line graphs, Toida-McKee's characterization of Eulerian graphs, the Tutte matrix of a graph, Fournier's proof of Kuratowski's theorem on planar graphs, the proof of the nonhamiltonicity of the Tutte graph on 46 vertices and a concrete application of triangulated graphs. The book does not presuppose deep knowledge of any branch of mathematics, but requires only the basics of mathematics. It can be used in an advanced undergraduate course or a beginning graduate course in graph theory.

### What people are saying -Write a review

User Review - Flag as inappropriate

Nearly all of the graph subjects are available in this book.
But the only and very important disadvantage of this book is that the subjects and materials are not dealt with and explained clearly and in detail.
Its not certainly a self study book, and it needs a teacher to explain the subjects.

User Review - Flag as inappropriate

بالا کریشنال

### Contents

 Basic Results ix 11 Basic Concepts x 12 Subgraphs 4 13 Degrees of Vertices 6 14 Paths and Connectedness 9 15 Automorphism of a Simple Graph 14 16 Line Graphs 16 17 Operations on Graphs 21
 65 2Factorable Graphs 120 66 Exercises 122 Notes 123 Graph Colorings 124 72 Critical Graphs 128 73 TriangleFree Graphs 132 74 Edge Colorings of Graphs 134 75 Snarks 140

 18 An Application to Chemistry 25 19 Miscellaneous Exercises 27 Notes 28 DIRECTED GRAPHS 29 22 Tournaments 31 23 kPartite Tournaments 34 Notes 39 Connectivity 40 32 Connectivity and EdgeConnectivity 44 33 Blocks 50 34 Cyclical EdgeConnectivity of a Graph 52 35 Mengers Theorem 53 36 Exercises 61 Notes 62 TREES 63 42 Centers and Centroids 68 43 Counting the Number of Spanning Trees 71 44 Cayleys Formula 75 45 Helly Property 76 46 Exercises 77 Notes 78 Independent Sets and Matchings 79 52 EdgeIndependent Sets 81 53 Matchings and Factors 83 54 Matchings in Bipartite Graphs 86 55 Perfect Matchings and the Tutte Matrix 95 Notes 97 EULERIAN AND HAMILTONIAN GRAPHS 98 62 Hamiltonian Graphs 103 63 Pancyclic Graphs 111 64 Hamilton Cycles in Line Graphs 114
 76 Kirkmans Schoolgirls Problem 141 77 Chromatic Polynomials 143 Notes 146 Planarity 148 82 Euler Formula and Its Consequences 153 83 K5 and K33 are Nonplanar Graphs 158 84 Dual of a Plane Graph 160 85 The FourColor Theorem and the Heawood FiveColor Theorem 163 86 Kuratowskis Theorem 166 87 Hamiltonian Plane Graphs 174 88 Tait Coloring 176 Notes 180 Triangulated Graphs 181 92 Triangulated Graphs 183 93 Interval Graphs 186 94 Bipartite Graph BG of a Graph G 188 95 Circular Arc Graphs 189 97 Phasing of Traffic Lights at a Road Junction 191 Notes 194 Applications 195 102 Kruskals Algorithm 196 103 Prims Algorithm 198 104 ShortestPath Problems 199 105 Timetable Problem 201 106 Application to Social Psychology 203 107 Exercises 206 List of Symbols 209 References 213 Index 219 Copyright