Content: Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
Preface
1 Graphs and Their Complements
1.1 Introduction
Exercises
1.2 Degree sequences
Exercises
1.3 Analysis
Exercises
1.4 Notes
2 Paths and Walks
2.1 Introduction
2.2 Complexity
Exercises
2.3 Walks
Exercises
2.4 The shortest-path problem
2.5 Weighted graphs and Dijkstra's algorithm
Exercises
2.6 Data structures
2.7 Floyd's algorithm
Exercises
2.8 Notes
3 Some Special Classes of Graphs
3.1 Bipartite graphs
Exercises
3.2 Line graphs
Exercises
3.3 Moore graphs
Exercises
3.4 Euler tours. 3.4.1 An Euler tour algorithmExercises
3.5 Notes
4 Trees and Cycles
4.1 Introduction 63 Exercises
4.2 Fundamental cycles
Exercises
4.3 Co-trees and bonds
Exercises
4.4 Spanning tree algorithms
4.4.1 Prim's algorithm
Data structures
Exercises
4.4.2 Kruskal's algorithm
Data structures and complexity
4.4.3 The Cheriton-Tarjan algorithm
Exercises
4.4.4 Leftist binary trees
Exercises
4.5 Notes
5 The Structure of Trees
5.1 Introduction
5.2 Non-rooted trees
Exercises
5.3 Read's tree encoding algorithm
5.3.1 The decoding algorithm
Exercises
5.4 Generating rooted trees. Exercises5.5 Generating non-rooted trees
Exercises
5.6 Priifer sequences
5.7 Spanning trees
5.8 The matrix-tree theorem
Exercises
5.9 Notes
6 Connectivity
6.1 Introduction
Exercises
6.2 Blocks
6.3 Finding the blocks of a graph
Exercises
6.4 The depth-first search
6.4.1 Complexity
Exercises
6.5 Notes
7 Alternating Paths and Matchings
7.1 Introduction
Exercises
7.2 The Hungarian algorithm
7.2.1 Complexity
Exercises
7.3 Perfect matchings and 1-factorizations
Exercises
7.4 The sub graph problem
7.5 Coverings in bipartite graphs
7.6 Tutte's theorem
Exercises
7.7 Notes. 8 Network Flows8.1 Introduction
8.2 The Ford-Fulkerson algorithm
Exercises
8.3 Matchings and flows
Exercises
8.4 Menger's theorems
Exercises
8.5 Disjoint paths and separating sets
Exercises
8.6 Notes
9 Hamilton Cycles
9.1 Introduction
Exercises
9.2 The crossover algorithm
9.2.1 Complexity
Exercises
9.3 The Hamilton closure
Exercises
9.4 The extended multi-path algorithm
9.4.1 Data structures for the segments
Exercises
9.5 Decision problems, NP-completeness
Exercises
9.6 The traveling salesman problem
Exercises
9.7 The TSP
9.8 Christofides' algorithm
Exercises. 9.9 Notes10 Digraphs
10.1 Introduction
10.2 Activity graphs, critical paths
10.3 Topological order
Exercises
10.4 Strong components
Exercises
10.4.1 An application to fabrics
Exercises
10.5 Tournaments
Exercises
10.6 2-Satisfiability
Exercises
10.7 Notes
11 Graph Colorings
11.1. Introduction
11.1.1 Intersecting lines in the plane
Exercises
11.2 Cliques
11.3 Mycielski's construction
11.4 Critical graphs
Exercises
11.5 Chromatic polynomials
Exercises
11.6 Edge colorings
11.6.1 Complexity
Exercises
11.7 NP-completeness
11.8 Notes
12 Planar Graphs
12.1 Introduction.