A Textbook of Graph Theory

Front Cover
Springer Science & Business Media, 2000 - Mathematics - 227 pages
3 Reviews
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

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information