o Home Page
o
About the Authors
....o Jonathan L. Gross
....o
Jay Yellen
o ORDER THE BOOKS
o
Graph Theory
.....Resources
....o
People
....o
Research
....o
Writings
....o
Conferences
....o
Journals
....o
The
Four-Color
....o Theorem
....o
White Pages
....o
White Pages
....o
Registration
o
Combinatorial Methods Toolkit
NEW!
o Feedback
o Site Correction
/
.....Change Request
o
Errata in GTAIA 2ed
o
Request an
.....Evaluation Copy
o
Graphsong
Last
Edited
13 Sep 2009
© 1999-2009
Aaron D. Gross
Email the Webmaster
 |
Graph TheoryTextbooks and Resources |
Graph Theory and Its Applications is a comprehensive applications-driven textbook that provides material for several different courses in graph theory.
1. INTRODUCTION to GRAPH MODELS
1.1 Graphs and Digraphs
1.2 Common Families of Graphs
1.3 Graph Modeling Applications
1.4 Walks and Distance
1.5 Paths, Cycles, and Trees
1.6 Vertex and Edge Attributes: More Applications
2. STRUCTURE and REPRESENTATION
2.1 Subgraphs
2.2 Some Graph Operations
2.3 Graph Isomorphism
2.4 Tests for Non-Isomorphism
2.5 Matrix Representations
3. TREES
3.1 Characterizations and Properties of Trees
3.2 Rooted Trees
3.3 Binary Trees
3.4 Counting Binary Trees: Catalan Recursion
3.5 Traversing a Binary Tree
3.6 Binary-Search Trees
3.7 Priority Trees
4. SPANNING TREES
4.1 An Intuitive Tree-Growing Scheme
4.2 Depth-First and Breadth-First Search
4.3 Applications of Depth-First Search
4.4 Counting Spanning Trees: Prüfer Encoding
4.5 Minimum Spanning Trees and Shortest Paths
4.6 Cycles, Edge-Cuts, and Spanning Trees
4.7 Graphs and Vector Spaces
4.8 Matroids and the Greedy Algorithm
5. CONNECTIVITY
5.1 Vertex- and Edge-Connectivity
5.2 Constructing Reliable Networks
5.3 Max-Min Duality and Menger's Theorems
5.4 Block Decompositions
6. OPTIMAL GRAPH TRANSVERSALS
6.1 Eulerian Trails and Tours
6.2 DeBruijn Sequences and Postman Problems
6.3 Hamiltonian Paths and Cycles
6.4 Gray Codes and Traveling Salesman Problems
7. GRAPH OPERATIONS and MAPPINGS
7.1 Binary Operations on Graphs
7.2 Linear Graph Mappings
7.3 Modeling Network Emulation
7.4 Subdivision and Homeomorphism
7.5 Transforming a Graph by Edge Contraction
8. DRAWING GRAPHS AND MAPS
8.1 The Topology of Graphs and of the Sphere
8.2 Higher-Order Surfaces
8.3 Drawing Imbeddings
8.4 Numerical Relations for Imbeddings
8.5 Regular Sphere Maps
9. PLANARITY OF GRAPHS
9.1 Planarity and Nonplanarity
9.2 Extending Planar Drawings
9.3 Kuratowski's Theorem
9.4 Planarity Algorithm
10. GRAPH COLORINGS
10.1 Vertex-Colorings
10.2 Map-Colorings
10.3 Edge-Colorings
11. SPECIAL DIGRAPH MODELS
11.1 Basic Properties and Some New Terminology
11.2 Selected Applications of the General Digraph
11.3 Tournaments and Project Scheduling
11.4 Finding the Strong Components of a Digraph
12. NETWORK FLOWS and APPLICATIONS
12.1 Flows and Cuts in Networks
12.2 Solving the Maximum-Flow Problem
12.3 Determining the Connectivity of a Graph
12.4 Matchings, Transversals, and Vertex Covers
13. GRAPHICAL ENUMERATION
13.1 Automorphisms and Symmetry
13.2 Graph Colorings and Symmetry
13.3 Cycle Index of a Permutation Group
13.4 Burnside's Lemma
13.5 Enumerating Vertex- and Edge-Colorings
13.6 Counting Simple Graphs
14. ALGEBRAIC SPECIFICATION of GRAPHS
14.1 Cyclic Voltages
14.2 Cayley Graphs and Regular Voltages
14.3 Permutation Voltages
14.4 Symmetric Graphs and Parallel Architectures
14.5 Interconnection-Network Performance
15. NONPLANAR LAYOUTS
15.1 Crossing Numbers and Thickness
15.2 Imbeddings in General Surfaces
15.3 Representing Imbeddings by Rotations
15.4 Genus Distribution of a Graph
15.5 Voltage-Graph Specification of Graph Layouts
15.6 Non-KVL Imbedded Voltage Graphs
15.7 Heawood Map-Coloring Problem
APPENDIX
A.1 Logic Fundamentals
A.2 Relations and Functions
A.3 Some Basic Combinatorics
A.4 Algebraic Structures
A.5 Algorithmic Complexity
A.6 Supplementary Reading
BIBLIOGRAPHY
B.1 General Reading
B.2 References
INDEXES
I.1 Index of Applications
I.2 Index of Algorithms
I.3 Index of Notations
I.4 General Index
PREFACE
Interest in graphs and their applications has grown exponentially in the past two decades, largely due to the usefulness of graphs as models for computation and optimization. This comprehensive introduction targets the need for a fresh approach to the theory, integrated with a careful exposition of emerging methods, models, and practical needs. It is suitable for classroom presentation at the introductory graduate or advanced undergraduate level, or for self-study and reference by working professionals.
Graph
theory has evolved as a collection of seemingly disparate
topics. The intent of the authors is to present this
material in a more cohesive framework, characteristic of
mathematical areas with longer traditions, such as linear
algebra and group theory. In the process, important
techniques and analytic tools are transformed into a
unified
mathematical methodology.
Emphasis throughout is conceptual, with more than 750 graph drawings included to strengthen intuition and more than 1600 exercises ranging from routine drill to more challenging problem solving. Applications and concrete examples are designed to stimulate interest in and demonstrate the relevance of new concepts.
Algorithms are written in a concise format, shorn of the details of computer implementation. Computer science students will find numerous projects inviting them to convert algorithms to computer programs. Software design issues are addressed throughout the book in the form of computational notes, which can be skipped by those not interested in implementation. These design issues include reusability and the user interface, as well as more familiar criteria of efficient use of computational resources.
Chapters 1 through 6 concentrate on modeling, representation, and basic properties. Graphical constructions here are always concrete and primarily spatial, with necessary abstractions introduced in a supportive role.
Chapters 7 through 12 broaden the scope. Chapter 7 introduces the concept of graph mapping and its relationship to network emulation, and Chapters 8 and 9 discuss drawings of graphs on surfaces. Chapters 10 through 12 concern several kinds of graph optimization problems: graph coloring, special digraph models, and network flow.
Some instructors of a one-semester course might consider leaving various sections of earlier chapters for self-study by students. This would allow more time for Chapters 13 through 15, which concern enumeration, specification by voltage graphs, and constructing nonplanar layouts.
Most of the material in Chapters 1 through 6 assumes no prerequisite. However, some familiarity with topics typically found in an undergraduate course in discrete mathematics would be useful, and those topics appear briefly in the appendix (along with some linear algebra, which is used in Section 4.7). The appendix provides a quick review (including permutation groups) for some of the more advanced topics in the later chapters.
Several different chapter sequences can make up a one-semester course. The definitions and results from Chapter 1, from Sections 2.1 through 2.4 of Chapter 2, and from Section 3.1 of Chapter 3 are used throughout the text, and they should be covered in any course that uses the book.
The remaining chapters are largely independent of each other, with several notable exceptions, as follows:
- Section 3.2 is used in Section 4.1.
- Sections 4.1 and 4.2 are used in Sections 5.4 and 11.4.
- Section 4.6 is referred to in Sections 5.3 and 6.1.
- Parts of Chapter 5 are used in Section 12.3.
- Chapter 8 and some definitions from Sections 7.1 and 7.4 are used in Chapter 9.
- Chapter 8 is used in Sections 15.1 through 15.4.
- Sections 14.1 through 14.3 are used in Sections 15.5 through 15.7.
A course oriented toward operations research/ optimization should include most or all of the material in Chapters 4 through 6 and 10 through 12, along with various other sections of the instructor's choice, depending on the time available. A course emphasizing the role of data structures and algorithms might add to the above topics the material in Chapter 3. A more general course in graph theory might replace some of the optimization and algorithmic material with selections from graph operations (Chapter 7), graph drawings (Chapter 8), planarity (Chapter 9), colorings (Chapter 10), enumeration (Chapter 13), voltage graphs (Chapter 14), or graphs on general surfaces (Chapter 15).
Several readers of our manuscript at various stages offered many helpful suggestions regarding the mathematical content. In particular, we would like to thank Bob Brigham, Jianer Chen, Lynn Kiaer, Ward Klein, Ben Manvel, Buck McMorris, Joe Straight, Tom Tucker, and Dav Zimak. We also thank Betsey Maupin for her proofreading and for her many stylistic suggestions.
585
Pages
ISBN: 0849339820
Price: $69.95
Publication Date: Dec 21 1998