Graph Theory and Its Applications, Second Edition: (Textbooks in Mathematics)

Interest in graphs and their applications has grown tremendously in recent years-largely due to the usefulness of graphs as models for computation and optimization. This comprehensive, applications-driven text provides a fresh and accessible approach suitable for several different courses in graph theory. Written for graduate and advanced undergraduate students, for self-study, and as a reference for working professionals, it covers a wide range of topics in algorithmic, combinatorial, and topological graph theory. The authors present numerous applications and examples designed to stimulate interest in and demonstrate the relevance of new concepts. With its generous use of drawings, streamlined proofs, and concise algorithms, Graph Theory and Its Applications offers a less intimidating treatment of the subject. It also includes more than 1,600 exercises-from routine to challenging-providing a rich source of problems that test your understanding. In this text, the authors succeed in presenting the subject in a cohesive framework that transforms important techniques and analytic tools into a unified mathematical methodology.

Table of Contents:
INTRODUCTION TO GRAPH MODELS Graphs and Digraphs Common Families of Graphs Graph Modeling Applications Walks and Distance Paths, Cycles, and Trees Vertex and Edge Attributes: More Applications STRUCTURE AND REPRESENTATION Subgraphs Some Graphs Operations Graph Isomorphism Tests for Non-Isomorphism Matrix Representations TREES Characterizations and Properties of Trees Rooted Trees Binary Trees Counting Binary Trees-The Catalan Recursion Traversing a Binary Tree Binary-Search Trees Priority Trees SPANNING TREES An Intuitive Tree-Growing Scheme Depth-First and Breadth-First Search Applications of Depth-First Search Counting Spanning Trees: Prüfer Encoding Minimum Spanning Trees and Shortest Paths Cycles, Edge Cuts, and Spanning Trees Graphs and Vector Spaces Matroids and the Greedy Algorithm CONNECTIVITY Vertex- and Edge-Connectivity Constructing Reliable Networks Max-Min Duality and Menger's Theorems Block Decomposition OPTIMAL GRAPH TRAVERSALS Eulerian Trails and Tours DeBruijn Sequences and Postman Problems Hamilton Paths and Cycles Gray Codes and Traveling Salesman Problems GRAPH OPERATIONS AND MAPPINGS Binary Operations on Graphs Linear Graph Mappings Modeling Network Emulation Subdivision and Homeomorphism Transforming a Graph by Edge Contraction DRAWING GRAPHS AND MAPS The Topology of Graphs and of the Sphere Higher-Order Surfaces Drawing Imbeddings Numerical Relations for Imbeddings Regular Sphere Maps PLANARITY OF GRAPHS Planarity and Nonplanarity Extending Planar Drawings Kuratowski's Theorem Planarity Algorithm GRAPH COLORINGS Vertex-Colorings Map-Colorings Edge-Colorings SPECIAL DIGRAPH MODELS Basic Properties and Some New Terminology Selected Applications of the General Digraph Tournaments and Project Scheduling Finding the Strong Components of a Digraph NETWORK FLOWS AND MATCHING Flows and Cuts in Networks Solving the Maximum-Flow Problem Determining the Connectivity of a Graph Matchings, Transversals, and Vertex Covers GRAPHICAL ENUMERATION Automorphisms and Symmetry Graph Colorings and Symmetry Cycle Index of a Permutation Group Burnside's Lemma Enumerating Vertex- and Edge-Colorings Counting Simple Graphs ALGEBRAIC SPECIFICATION OF GRAPHS Cyclic Voltages Cayley Graphs and Regular Voltages Permutation Voltages Symmetric Graphs and Parallel Architectures Interconnection-Network Performance NON-PLANAR LAYOUTS Crossing Numbers and Thickness Imbeddings in General Surfaces Representing Imbeddings by Rotations Genus Distribution of a Graph Voltage-Graph Specification of Graph Layouts Non-KVL Imbedded Voltage Graphs Heawood Map-Coloring Problem APPENDICES Logic Fundamentals Relations and Functions Some Basic Combinatorics Algebraic Structures Algorithmic Complexity Supplementary Reading BIBLIOGRAPHY INDICES Index of Applications Index of Algorithms Index of Notations General Index

About the Author :
Gross; Jonathan L. Columbia University, New York, New York, USA,Yellen; Jay Rollins College, Winter Park, Florida, USA,