Graph Theory and Its Applications, Second Edition

✍ Scribed by Gross, Jonathan L.; Yellen, Jay

• Publisher: CRC Press
• Year: 2005
• Tongue: English
• Leaves: 799
• Series: Textbooks in Mathematics
• Edition: 2nd ed
• Category: Library

✦ Synopsis

INTRODUCTION TO GRAPH MODELSGraphs and DigraphsCommon Families of GraphsGraph Modeling ApplicationsWalks and DistancePaths, Cycles, and TreesVertex and Edge Attributes: More ApplicationsSTRUCTURE AND REPRESENTATIONGraph IsomorphismRevised!Automorphisms and Symmetry Moved and revised!SubgraphsSome Graph OperationsTests for Non-IsomorphismMatrix RepresentationMore Graph OperationsTREESReorganized and revised!Characterizations and Properties of TreesRooted Trees, Ordered Trees, and Binary TreesBinary-Tree TraversalsBinary-Search TreesHuffman Trees and Optimal Prefix CodesPriority TreesCounting Labeled Trees: Prüfer EncodingCounting Binary Trees: Catalan RecursionSPANNING TREES Reorganized and revised!Tree-GrowingDepth-First and Breadth-First SearchMinimum Spanning Trees and Shortest PathsApplications of Depth-First SearchCycles, Edge Cuts, and Spanning TreesGraphs and Vector SpacesMatroids and the Greedy AlgorithmCONNECTIVITYRevised!Vertex- and Edge-ConnectivityConstructing Reliable NetworksMax-Min Duality and Menger's TheoremsBlock DecompositionsOPTIMAL GRAPH TRAVERSALSEulerian Trails and ToursDeBruijn Sequences and Postman ProblemsHamiltonian Paths and CyclesGray Codes and Traveling Salesman ProblemsPLANARITY AND KURATOWSKI'S THEOREMReorganized and revised!Planar Drawings and Some Basic SurfacesSubdivision and HomeomorphismExtending Planar DrawingsKuratowski's TheoremAlgebraic Tests for PlanarityPlanarity AlgorithmCrossing Numbers and ThicknessDRAWING GRAPHS AND MAPSReorganized and revised!The Topology of Low DimensionsHigher-Order SurfacesMathematical Model for Drawing GraphsRegular Maps on a SphereImbeddings on Higher-Order SurfacesGeometric Drawings of GraphsNew!GRAPH COLORINGSVertex-ColoringsMap-ColoringsEdge-ColoringsFactorization New!MEASUREMENT AND MAPPINGS New Chapter!Distance in Graphs New!Domination in Graphs New!Bandwidth.

New!Intersection Graphs New!Linear Graph MappingsMoved and revised!Modeling Network EmulationMoved and revised!ANALYTIC GRAPH THEORY New Chapter!Ramsey Graph Theory New!Extremal Graph Theory New!Random Graphs New!SPECIAL DIGRAPH MODELS Reorganized and revised!Directed Paths and Mutual ReachabilityDigraphs as Models for RelationsTournamentsProject Scheduling and Critical PathsFinding the Strong Components of a DigraphNETWORK FLOWS AND APPLICATIONSFlows and Cuts in NetworksSolving the Maximum-Flow ProblemFlows and ConnectivityMatchings, Transversals, and Vertex CoversGRAPHICAL ENUMERATION Reorganized and revised!Automorphisms of Simple GraphsGraph Colorings and SymmetryBurnside's LemmaCycle-Index Polynomial of a Permutation GroupMore Counting, Including Simple GraphsPolya-Burnside EnumerationALGEBRAIC SPECIFICATION OF GRAPHSCyclic VoltagesCayley Graphs and Regular VoltagesPermutation VoltagesSymmetric Graphs and Parallel ArchitecturesInterconnection-Network PerformanceNON-PLANAR LAYOUTS Reorganized and revised!Representing Imbeddings by RotationsGenus Distribution of a GraphVoltage-Graph Specification of Graph LayoutsNon KVL Imbedded Voltage GraphsHeawood Map-Coloring ProblemAPPENDIXLogic FundamentalsRelations and FunctionsSome Basic CombinatoricsAlgebraic StructuresAlgorithmic ComplexitySupplementary ReadingBIBLIOGRAPHYGeneral ReadingReferencesSOLUTIONS AND HINTSNew!INDEXESIndex of ApplicationsIndex of AlgorithmsIndex of NotationsGeneral Index.  Read more...

Abstract:

Dealing with graph theory, this book includes chapters on measurement and analytic graph theory. It takes a comprehensive approach to graph theory that integrates an exposition of classical developments with various methods, models, and practical needs.  Read more...

✦ Table of Contents

Content: Front cover --
PREFACE --
ABOUT THE AUTHORS --
Dedication --
CONTENTS --
Chapter 1. INTRODUCTION TO GRAPH MODELS --
Chapter 2. STRUCTURE AND REPRESENTATION --
Chapter 3. TREES --
Chapter 4. SPANNING TREES --
Chapter 5. CONNECTIVITY --
Chapter 6. OPTIMAL GRAPH TRAVERSALS --
Chapter 7. PLANARITY AND KURATOWSKI'S THEOREM --
Chapter 8. DRAWING GRAPHS AND MAPS --
Chapter 9. GRAPH COLORINGS --
Chapter 10. MEASUREMENT AND MAPPINGS --
Chapter 11. ANALYTIC GRAPH THEORY --
Chapter 12. SPECIAL DIGRAPH MODELS --
Chapter 13. NETWORK FLOWS AND APPLICATIONS --
Chapter 14. GRAPHICAL ENUMERATION --
Chapter 15. ALGEBRAIC SPECIFICATION OF GRAPHS --
Chapter 16. NONPLANAR LAYOUTS --
APPENDIX --
BIBLIOGRAPHY --
SOLUTIONS AND HINTS --
Back cover.

✦ Subjects

Graph theory.