A First Course in Graph Theory

Description

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. 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