## A Textbook of Graph TheoryGraph 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 |

219 | |

### Other editions - View all

### Common terms and phrases

1-factor 2-connected algorithm belongs bipartite graph chromatic number cliques of G complete graph components of G connected graph contradiction Corollary corresponding cubic graph cut edge cut vertex cycle of G Definition degree sequence deletion denoted digraph directed 3-cycles edge cut edge of G edge-disjoint edges incident end vertices Exercise G contains G is called G is connected Graph for proof graph G graph of Figure graph theory Hamilton cycle Hamilton path Hamiltonian graph Hence homeomorph independent set induced subgraph interval graph isomorphic Kirkman's schoolgirls problem least three vertices Lemma minimum number nonadjacent vertices number of edges number of vertices path in G Petersen graph planar graph plane embedding problem Proof Let G proof of Theorem Prove result simple connected graph simple graph spanning subgraph spanning tree subgraph of G subset tournament triangulated graph u-v path vertex coloring vertex of degree vertex of G vertex set y)-paths