Graph Theory and Its Applications, Second Edition

by Gross; Jonathan L.

• ISBN13: 9781584885054
• ISBN10: 158488505X
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-09-22
• Publisher: Chapman & Hall/

Summary

Already an international bestseller, with the release of this greatly enhanced second edition, Graph Theory and Its Applications is now an even better choice as a textbook for a variety of courses -- a textbook that will continue to serve your students as a reference for years to come.The superior explanations, broad coverage, and abundance of illustrations and exercises that positioned this as the premier graph theory text remain, but are now augmented by a broad range of improvements. Nearly 200 pages have been added for this edition, including nine new sections and hundreds of new exercises, mostly non-routine.What else is new?· New chapters on measurement and analytic graph theory· Supplementary exercises in each chapter - ideal for reinforcing, reviewing, and testing.· Solutions and hints, often illustrated with figures, to selected exercises - nearly 50 pages worth· Reorganization and extensive revisions in more than half of the existing chapters for smoother flow of the exposition· Foreshadowing - the first three chapters now preview a number of concepts, mostly via the exercises, to pique the interest of readerGross and Yellen take a comprehensive approach to graph theory that integrates careful exposition of classical developments with emerging methods, models, and practical needs. Their unparalleled treatment provides a text ideal 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.

Table of Contents

Preface
Introduction to Graph Models	1	(56)
Graphs and Digraphs	2	(13)
Common Families of Graphs	15	(7)
Graph Modeling Applications	22	(6)
Walks and Distance	28	(11)
Paths, Cycles, and Trees	39	(9)
Vertex and Edge Attributes: More Applications	48	(3)
Supplementary Exercises	51	(6)
Glossary	53	(4)
Structure and Representation	57	(58)
Graph Isomorphism	58	(7)
Automorphisms and Symmetry	65	(7)
Subgraphs	72	(8)
Some Graph Operations	80	(9)
Tests for Non-Isomorphism	89	(6)
Matrix Representations	95	(6)
More Graph Operations	101	(6)
Supplementary Exercises	107	(8)
Glossary	110	(5)
Trees	115	(48)
Characterizations and Properties of Trees	116	(8)
Rooted Trees, Ordered Trees, and Binary Trees	124	(8)
Binary-Tree Traversals	132	(5)
Binary-Search Trees	137	(4)
Huffman Trees and Optimal Prefix Codes	141	(5)
Priority Trees	146	(5)
Counting Labeled Trees: Prufer Encoding	151	(5)
Counting Binary Trees: Catalan Recursion	156	(2)
Supplementary Exercises	158	(5)
Glossary	160	(3)
Spanning Trees	163	(54)
Tree Growing	164	(7)
Depth-First and Breadth-First Search	171	(5)
Minimum Spanning Trees and Shortest Paths	176	(6)
Applications of Depth-First Search	182	(8)
Cycles, Edge-Cuts, and Spanning Trees	190	(7)
Graphs and Vector Spaces	197	(10)
Matroids and the Greedy Algorithm	207	(5)
Supplementary Exercises	212	(5)
Glossary	213	(4)
Connectivity	217	(30)
Vertex- and Edge-Connectivity	218	(5)
Constructing Reliable Networks	223	(8)
Max-Min Duality and Menger's Theorems	231	(10)
Block Decompositions	241	(3)
Supplementary Exercises	244	(3)
Glossary	245	(2)
Optimal Graph Traversals	247	(38)
Eulerian Trails and Tours	248	(4)
DeBruijn Sequences and Postman Problems	252	(15)
Hamiltonian Paths and Cycles	267	(6)
Gray Codes and Traveling Salesman Problems	273	(9)
Supplementary Exercises	282	(3)
Glossary	283	(2)
Planarity and Kuratowski's Theorem	285	(52)
Planar Drawings and Some Basic Surfaces	286	(6)
Subdivision and Homeomorphism	292	(5)
Extending Planar Drawings	297	(7)
Kuratowski's Theorem	304	(7)
Algebraic Tests for Planarity	311	(13)
Planarity Algorithm	324	(3)
Crossing Numbers and Thickness	327	(4)
Supplementary Exercises	331	(6)
Glossary	334	(3)
Drawing Graphs and Maps	337	(34)
The Topology of Low Dimensions	338	(3)
Higher-Order Surfaces	341	(5)
Mathematical Model for Drawing Graphs	346	(3)
Regular Maps on a Sphere	349	(5)
Imbeddings on Higher-Order Surfaces	354	(7)
Geometric Drawings of Graphs	361	(4)
Supplementary Exercises	365	(6)
Glossary	366	(5)
Graph Colorings	371	(46)
Vertex-Colorings	372	(14)
Map-Colorings	386	(7)
Edge-Colorings	393	(14)
Factorization	407	(4)
Supplementary Exercises	411	(6)
Glossary	413	(4)
Measurement and Mappings	417	(52)
Distance in Graphs	418	(6)
Domination in Graphs	424	(6)
Bandwidth	430	(5)
Intersection Graphs	435	(9)
Linear Graph Mappings	444	(9)
Modeling Network Emulation	453	(9)
Supplementary Exercises	462	(7)
Glossary	463	(6)
Analytic Graph Theory	469	(24)
Ramsey Graph Theory	470	(5)
Extremal Graph Theory	475	(5)
Random Graphs	480	(9)
Supplementary Exercises	489	(4)
Glossary	490	(3)
Special Digraph Models	493	(40)
Directed Paths and Mutual Reachability	494	(11)
Digraphs as Models for Relations	505	(6)
Tournaments	511	(5)
Project Scheduling and Critical Paths	516	(7)
Finding the Strong Components of a Digraph	523	(5)
Supplementary Exercises	528	(5)
Glossary	529	(4)
Network Flows and Applications	533	(44)
Flows and Cuts in Networks	534	(8)
Solving the Maximum-Flow Problem	542	(9)
Flows and Connectivity	551	(9)
Matchings, Transversals, and Vertex Covers	560	(13)
Supplementary Exercises	573	(4)
Glossary	574	(3)
Graphical Enumeration	577	(36)
Automorphisms of Simple Graphs	578	(5)
Graph Colorings and Symmetry	583	(6)
Burnside's Lemma	589	(6)
Cycle-Index Polynomial of a Permutation Group	595	(5)
More Counting, Including Simple Graphs	600	(6)
Polya-Burnside Enumeration	606	(3)
Supplementary Exercises	609	(4)
Glossary	610	(3)
Algebraic Specification of Graphs	613	(38)
Cyclic Voltages	614	(9)
Cayley Graphs and Regular Voltages	623	(9)
Permutation Voltages	632	(5)
Symmetric Graphs and Parallel Architectures	637	(7)
Interconnection-Network Performance	644	(2)
Supplementary Exercises	646	(5)
Glossary	649	(2)
Nonplanar Layouts	651	(30)
Representing Imbeddings by Rotations	652	(7)
Genus Distribution of a Graph	659	(5)
Voltage-Graph Specification of Graph Layouts	664	(6)
Non-KVL Imbedded Voltage Graphs	670	(2)
Heawood Map-Coloring Problem	672	(5)
Supplementary Exercises	677	(4)
Glossary	678	(3)
APPENDIX	681	(14)
A.1 Logic Fundamentals	681	(2)
A.2 Relations and Functions	683	(3)
A.3 Some Basic Combinatorics	686	(1)
A.4 Algebraic Structures	687	(5)
A.5 Algorithmic Complexity	692	(2)
A.6 Supplementary Reading	694	(1)
BIBLIOGRAPHY	695	(14)
General Reading	695	(2)
References	697	(12)
SOLUTIONS and HINTS	709	(48)
INDEXES	757	(1)
Index of Applications	757	(2)
Index of Algorithms	759	(2)
Index of Notations	761	(6)
General Index	767