A First Course in Graph Theory

✍ Scribed by Gary Chartrand, Ping Zhang

• Publisher: Dover Publications
• Year: 2012
• Tongue: English
• Leaves: 466
• Series: Dover Books on Mathematics
• Category: Library

✦ Synopsis

This comprehensive text offers undergraduates a remarkably student-friendly introduction to graph theory. Written by two of the field's most prominent experts, it takes an engaging approach that emphasizes graph theory's history. Unique examples and lucid proofs provide a sound yet accessible treatment that stimulates interest in an evolving subject and its many applications.
Optional sections designated as "excursion" and "exploration" present interesting sidelights of graph theory and touch upon topics that allow students the opportunity to experiment and use their imaginations. Three appendixes review important facts about sets and logic, equivalence relations and functions, and the methods of proof. The text concludes with solutions or hints for odd-numbered exercises, in addition to references, indexes, and a list of symbols.

✦ Table of Contents

Cover
Title Page
Copyright Page
Table of Contents
Preface
1. Introduction
1.1. Graphs and Graph Models
1.2. Connected Graphs
1.3. Common Classes of Graphs
1.4. Multigraphs and Digraphs
2. Degrees
2.1. The Degree of a Vertex
2.2. Regular Graphs
2.3. Degree Sequences
2.4. Excursion: Graphs and Matrices
2.5. Exploration: Irregular Graphs
3. Isomorphic Graphs
3.1. The Definition of Isomorphism
3.2. Isomorphism as a Relation
3.3. Excursion: Graphs and Groups
3.4. Excursion: Reconstruction and Solvability
4. Trees
4.1. Bridges
4.2. Trees
4.3. The Minimum Spanning ‘Tree Problem
4.4. Excursion: The Number of Spanning Trees
5. Connectivity
5.1. Cut-Vertices
5.2. Blocks
5.3. Connectivity
5.4. Menger’s ‘Theorem
5.5. Exploration: Powers and Edge Labelings
6. Traversability
6.1. Eulerian Graphs
6.2. Hamiltonian Graphs
6.3. Exploration: Hamiltonian Walks
6.4. Excursion: Early Books of Graph Theory
7.Digraphs
7.1. Strong Digraphs
7.2. ‘Tournaments
7.3. Excursion: Decision-Making
7.4. Exploration: Wine Bottle Problems
8. Matchings and Factorization
8.1. Matchings
8.2. Factorization
8.3. Decompositions and Graceful Labelings
8.4. Excursion: Instant Insanity
8.5. Excursion: ‘The Petersen Graph
8.6. Exploration: Bi-Graceful Graphs
9. Planarity
9.1. Planar Graphs
9.2. Embedding Graphs on Surfaces
9.3. Excursion: Graph Minors
9.4. Exploration: Embedding Graphs in Graphs
10. Coloring Graphs
10.1. ‘The Four Color Problem
10.2. Vertex Coloring
10.3. Edge Coloring
10.4. Excursion: ‘The Heawood Map Coloring Theorem
10.5. Exploration: Modular Coloring
11. Ramsey Numbers
11.1. The Ramsey Number of Graphs
11.2. Turan’s Theorem
11.3. Exploration: Modified Ramsey Numbers
11.4. Excursion: Erdos Numbers
12. Distance
12.1. The Center of a Graph
12.2. Distant Vertices
12.3. Excursion: Locating Numbers
12.4. Excursion: Detour and Directed Distance
12.5. Exploration: Channel Assignment
12.6. Exploration: Distance Between Graphs
13. Domination
13.1. The Domination Number of a Graph
13.2. Exploration: Stratification
13.3. Exploration: Lights Out
13.4. Excursion: And Still It Grows More Colorful
Appendix 1. Sets and Logic
Appendix 2. Equivalence Relations and Functions
Appendix 3. Methods of Proof
Solutions and Hints for Odd-Numbered Exercises
References
Index of Names
Index of Mathematical Terms
List of Symbols