Graphs & Digraphs

Cover
Half Title
Series Page
Title Page
Copyright Page
Contents
Preface to the seventh edition
About the authors
1. Graphs
	1.1. Fundamentals
	1.2. Isomorphism
	1.3. Families of graphs
	1.4. Operations on graphs
	1.5. Degree sequences
	1.6. Path and cycles
	1.7. Connected graphs and distance
	1.8. Trees and forests
	1.9. Multigraphs and pseudographs
	Exercises
2. Digraphs
	2.1. Fundamentals
	2.2. Strongly connected digraphs
	2.3. Tournaments
	2.4. Score sequences
	Exercises
3. Traversability
	3.1. Eulerian graphs and digraphs
	3.2. Hamiltonian graphs
	3.3. Hamiltonian digraphs
	3.4. Highly hamiltonian graphs
	3.5. Graph powers
	Exercises
4. Connectivity
	4.1. Cut-vertices, bridges, and blocks
	4.2. Vertex connectivity
	4.3. Edge-connectivity
	4.4. Menger\'s theorem
	Exercises
5. Planarity
	5.1. Euler\'s formula
	5.2. Characterizations of planarity
	5.3. Hamiltonian planar graphs
	5.4. The crossing number of a graph
	Exercises
6. Coloring
	6.1. Vertex coloring
	6.2. Edge coloring
	6.3. Critical and perfect graphs
	6.4. Maps and planar graphs
	Exercises
7. Flows
	7.1. Networks
	7.2. Max-flow min-cut theorem
	7.3. Menger\'s theorems for digraphs
	7.4. A connection to coloring
	Exercises
8. Factors and covers
	8.1. Matchings and 1-factors
	8.2. Independence and covers
	8.3. Domination
	8.4. Factorizations and decompositions
	8.5. Labelings of graphs
	Exercises
9. Extremal graph theory
	9.1. Avoiding a complete graph
	9.2. Containing cycles and trees
	9.3. Ramsey theory
	9.4. Cages and Moore graphs
	Exercises
10. Embeddings
	10.1. The genus of a graph
	10.2. 2-Cell embeddings of graphs
	10.3. The maximum genus of a graph
	10.4. The graph minor theorem
	Exercises
11. Graphs and algebra
	11.1. Graphs and matrices
	11.2. The automorphism group
	11.3. Cayley color graphs
	11.4. The reconstruction problem
	Exercises
Hints to selected exercises
Bibliography
Index