Graph Theory and Its Applications (Textbooks in Mathematics)

✍ Scribed by Jonathan L. Gross, Jay Yellen, Mark Anderson

• Publisher: Chapman and Hall/CRC
• Year: 2018
• Tongue: English
• Leaves: 593
• Series: Textbooks in Mathematics
• Edition: 3
• Category: Library

✦ Synopsis

Graph Theory and Its Applications, Third Edition is the latest edition of the international, bestselling textbook for undergraduate courses in graph theory, yet it is expansive enough to be used for graduate courses as well. The textbook takes a comprehensive, accessible approach to graph theory, integrating careful exposition of classical developments with emerging methods, models, and practical needs.

The authors’ unparalleled treatment is an ideal text for a two-semester course and a variety of one-semester classes, from an introductory one-semester course to courses slanted toward classical graph theory, operations research, data structures and algorithms, or algebra and topology.

Features of the Third Edition

• Expanded coverage on several topics (e.g., applications of graph coloring and tree-decompositions)
• Provides better coverage of algorithms and algebraic and topological graph theory than any other text
• Incorporates several levels of carefully designed exercises that promote student retention and develop and sharpen problem-solving skills
• Includes supplementary exercises to develop problem-solving skills, solutions and hints, and a detailed appendix, which reviews the textbook’s topics

About the Authors

Jonathan L. Gross is a professor of computer science at Columbia University. His research interests include topology and graph theory.

Jay Yellen is a professor of mathematics at Rollins College. His current areas of research include graph theory, combinatorics, and algorithms.

Mark Anderson is also a mathematics professor at Rollins College. His research interest in graph theory centers on the topological or algebraic side.

✦ Table of Contents

Cover
Half Title
Textbooks in Mathematics
Title
Copyright
Dedication
CONTENTS
PREFACE
AUTHORS
Chapter 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
1.7 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 2 STRUCTURE AND REPRESENTATION
2.1 GRAPH ISOMORPHISM
2.2 AUTOMORPHISMS AND SYMMETRY
2.3 SUBGRAPHS
2.4 SOME GRAPH OPERATIONS
2.5 TESTS FOR NON-ISOMORPHISM
2.6 MATRIX REPRESENTATIONS
2.7 MORE GRAPH OPERATIONS
2.8 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 3 TREES
3.1 CHARACTERIZATIONS AND PROPERTIES OF TREES
3.2 ROOTED TREES, ORDERED TREES, AND BINARY TREES
3.3 BINARY-TREE TRAVERSALS
3.4 BINARY-SEARCH TREES
3.5 HU MAN TREES AND OPTIMAL PRE X CODES
3.6 PRIORITY TREES
3.7 COUNTING LABELED TREES: PR UFER ENCODING
3.8 COUNTING BINARY TREES: CATALAN RECURSION
3.9 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 4 SPANNING TREES
4.1 TREE GROWING
4.2 DEPTH-FIRST AND BREADTH-FIRST SEARCH
4.3 MINIMUM SPANNING TREES AND SHORTEST PATHS
4.4 APPLICATIONS OF DEPTH-FIRST SEARCH
4.5 CYCLES, EDGE-CUTS, AND SPANNING TREES
4.6 GRAPHS AND VECTOR SPACES
4.7 MATROIDS AND THE GREEDY ALGORITHM
4.8 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 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
5.5 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 6 OPTIMAL GRAPH TRAVERSALS
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
6.5 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 7 PLANARITY AND KURATOWSKI'S THEOREM
7.1 PLANAR DRAWINGS AND SOME BASIC SURFACES
7.2 SUBDIVISION AND HOMEOMORPHISM
7.3 EXTENDING PLANAR DRAWINGS
7.4 KURATOWSKI'S THEOREM
7.5 ALGEBRAIC TESTS FOR PLANARITY
7.6 PLANARITY ALGORITHM
7.7 CROSSING NUMBERS AND THICKNESS
7.8 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 8 GRAPH COLORINGS
8.1 VERTEX-COLORINGS
8.2 MAP-COLORINGS
8.3 EDGE-COLORINGS
8.4 FACTORIZATION
8.5 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 9 SPECIAL DIGRAPH MODELS
9.1 DIRECTED PATHS AND MUTUAL REACHABILITY
9.2 DIGRAPHS AS MODELS FOR RELATIONS
9.3 TOURNAMENTS
9.4 PROJECT SCHEDULING
9.5 FINDING THE STRONG COMPONENTS OF A DIGRAPH
9.6 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 10 NETWORK FLOWS AND APPLICATIONS
10.1 FLOWS AND CUTS IN NETWORKS
10.2 SOLVING THE MAXIMUM-FLOW PROBLEM
10.3 FLOWS AND CONNECTIVITY
10.4 MATCHINGS, TRANSVERSALS, AND VERTEX COVERS
10.5 SUPPLEMENTARY EXERCISES
GLOSSARY
Chapter 11 GRAPH COLORINGS AND SYMMETRY
11.1 AUTOMORPHISMS OF SIMPLE GRAPHS
11.2 EQUIVALENCE CLASSES OF COLORINGS
11.3 SUPPLEMENTARY EXERCISES
GLOSSARY
A 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
B BIBLIOGRAPHY
B.1 GENERAL READING
B.2 REFERENCES
SOLUTIONS AND HINTS
INDEX OF APPLICATIONS
INDEX OF ALGORITHMS
GENERAL INDEX