book

Handbook of Graph Theory, 2nd Edition

by Jonathan L. Gross, Jay Yellen, Ping Zhang

December 2013

Intermediate to advanced

1630 pages

46h

English

Chapman and Hall/CRC

Read now

Unlock full access

Preliminaries
Discrete Mathematics and its Applications
Dedication
Preface
FormatTerminology and NotationAcknowledgments
About the Editors
Contributors
Chapter 1 Introduction to Graphs
Section 1.1 Fundamentals of Graph Theory1.1.1 Graphs and DigraphsBasic TerminologySimple GraphsEdge Notation for Simple Adjacencies and for Multi-EdgesGeneral GraphsAttributesDigraphsOrdered-Pair Representation of ArcsVertex-Coloring1.1.2 Degree and DistanceDegreeWalks, Trails, and PathsDistance and Connectivity1.1.3 Basic Structural ConceptsIsomorphismAutomorphismsSubgraphsGraph Operations1.1.4 TreesAcyclic GraphsTrees as SubgraphsBasic Tree-Growing AlgorithmPrioritizing the Edge SelectionReferencesSection 1.2 Families of Graphs and Digraphs1.2.1 Building Blocks1.2.2 SymmetryLocal Symmetry: RegularityGlobal Symmetry: Vertex-Transitivity1.2.3 Integer-Valued InvariantsCycle RankChromatic Number and k-Partite GraphsK-Connectivity and K-Edge-ConnectivityMinimum Genus1.2.4 Criterion QualificationReferencesSection 1.3 History of Graph Theory1.3.1 TraversabilityThe Königsberg Bridges ProblemDiagram-Tracing PuzzlesHamiltonian Graphs1.3.2 TreesCounting TreesChemical Trees1.3.3 Topological GraphsEuler's Polyhedron FormulaPlanar GraphsGraphs on Higher Surfaces1.3.4 Graph ColoringsThe Four-Color ProblemOther Graph Coloring ProblemsFactorization1.3.5 Graph AlgorithmsReferencesGlossary for Chapter 1Figure 1.1.1Figure 1.1.2Figure 1.1.3Figure 1.1.4Figure 1.1.5Figure 1.1.6Figure 1.1.7Figure 1.1.8Figure 1.1.9Figure 1.1.10Figure 1.1.11Figure 1.1.12Figure 1.1.13Figure 1.1.14Figure 1.1.15Figure 1.1.16Figure 1.1.17Figure 1.1.18Figure 1.1.19Figure 1.1.20Figure 1.1.21Figure 1.1.22Figure 1.2.1Figure 1.2.2Figure 1.2.3Figure 1.2.4Figure 1.2.5Figure 1.2.6Figure 1.2.7Figure 1.2.8Figure 1.2.9Figure 1.2.10Figure 1.3.1Figure 1.3.2Figure 1.3.3Figure 1.3.4Figure 1.3.5Figure 1.3.6Figure 1.3.7Figure 1.3.8Figure 1.3.9Figure 1.3.10Figure 1.3.11Figure 1.3.12Figure 1.3.13
Chapter 2 Graph Representation
Section 2.1 Computer Representations of Graphs2.1.1 Basic Representations for Graphs2.1.2 Graph Traversal AlgorithmsDepth-First SearchBreadth-First Search2.1.3 All-Pairs ProblemsAll-Pairs Shortest-Paths AlgorithmTransitive Closure2.1.4 Applications to Pattern MatchingKleene's AlgorithmReferencesSection 2.2 Graph Isomorphism2.2.1 Isomorphisms and AutomorphismsBasic TerminologyRelated Isomorphism Problems2.2.2 Complexity Theory2.2.3 AlgorithmsSearch TreeSoftwareReferencesSection 2.3 The Reconstruction Problem2.3.1 Two Reconstruction ConjecturesDecks and Edge-DecksReconstructibilityThe Reconstruction ConjectureThe Edge-Reconstruction ConjectureComparing Reconstruction with Edge-ReconstructionReconstruction and Graph Symmetries2.3.2 Some Reconstructible Parameters and ClassesReconstructible ParametersReconstructible Classes2.3.3 Reconstructing from Less than the Full DeckEndvertex-ReconstructionReconstruction NumbersSet ReconstructionReconstruction from the Characteristic Polynomial DeckReconstructing from k-Vertex-Deleted Subgraphs2.3.4 Tutte's and Kocay's ResultsKocay's ParameterCharacteristic and Chromatic Polynomials2.3.5 Lovász's Method and Nash–Williams's LemmaThe Nash–Williams LemmaStructures Other than GraphsThe Reconstruction Index of Groups2.3.6 Digraphs2.3.7 Illegitimate Decks2.3.8 Recent ResultsReferencesSection 2.4 Recursively Constructed Graphs2.4.1 Some Parameterized Families of Graph ClassesTreesSeries-Parallel Graphsk-Trees and Partial k-TreesHalin GraphsBandwidth-k GraphsTreewidth-k GraphsPathwidth-k GraphsBranchwidth-k Graphsk-Terminal GraphsCographsCliquewidth-k Graphsk-NLC Graphsk-HB Graphs2.4.2 Equivalences and CharacterizationsRelationships between Recursive ClassesCharacterizations2.4.3 RecognitionRecognition of Recursive ClassesReferencesSection 2.5 Structural Graph Theory2.5.1 Perfect GraphsANOTHER FACT, ALSO FIRST CONJECTURED BY BERGEOutline of the Proof of the Strong Perfect Graph Theorem2.5.2 Other Decomposition Theorems2.5.3 Structure TheoremsClaw-Free GraphsQuasi-Line GraphsBull-Free GraphsINFORMAL DEFINITIONS2.5.4 TrigraphsUsing Trigraphs: Structure TheoremsUsing Trigraphs: Algorithms2.5.5 Recognition AlgorithmsTesting for Pyramids: the Shortest Paths DetectorEasily Detectable Configurations; Cleaning; Finding Odd HolesTesting for Even HolesMore AlgorithmsThe Three-in-a-Tree Problem2.5.6 Erdős-Hajnal Conjecture and χ-BoundednessTournamentsχ-Boundedness2.5.7 Well-Quasi-Ordering and Rao's ConjectureOutline of the Proof of Fact F402.5.8 Tournament ImmersionOn the Proof of Fact F462.5.9 Topological Containment in Tournaments2.5.10 Disjoint Paths Problems in TournamentsThe Edge-Disjoint Paths ProblemThe Vertex-Disjoint Paths Problem2.5.11 AcknowledgmentReferencesGlossary for Chapter 2Figure 2.1.1Figure 2.2.1Figure 2.2.2Figure 2.2.3Figure 2.2.4Figure 2.3.1Figure 2.4.1Figure 2.4.2Figure 2.4.3Figure 2.4.4Figure 2.4.5Figure 2.4.6Figure 2.4.7Figure 2.4.8Figure 2.4.9Figure 2.4.10Figure 2.4.11Figure 2.4.12Figure 2.4.13Figure 2.4.14Figure 2.4.15Figure 2.4.16Figure 2.4.17Figure 2.5.1
Chapter 3 Directed Graphs
Section 3.1 Basic Digraph Models and Properties3.1.1 Terminology and Basic FactsReachability and ConnectivityMeasures of Digraph ConnectivityDirected TreesTree-Growing in a DigraphOriented GraphsAdjacency Matrix of a Digraph3.1.2 A Sampler of Digraph ModelsMarkov Chains and Markov DigraphsEquipment-Replacement PolicyThe Digraph of a Relation and the Transitive ClosureConstructing the Transitive Closure of a Digraph: AlgorithmActivity-Scheduling NetworksScheduling the Matches in a Round-Robin TournamentFlows in NetworksSoftware Testing and the Chinese Postman ProblemLexical Scanners3.1.3 Binary TreesRooted Tree TerminologyBinary SearchReferencesSection 3.2 Directed Acyclic Graphs3.2.1 Examples and Basic Facts3.2.2 Rooted TreesDefinitions for Rooted TreesSpanning Directed TreesFunctional Graphs3.2.3 DAGs and Posets3.2.4 Topological Sort and OptimizationOptimizationReferencesSection 3.3 Tournaments3.3.1 Basic Definitions and ExamplesRegular TournamentsArc Reversals3.3.2 Paths, Cycles, and ConnectivityCondensation and Transitive TournamentsCycles and Paths in TournamentsHamiltonian Cycles and Kelly’s ConjectureHigher ConnectivityAnti-Directed Paths3.3.3 Scores and Score SequencesThe Second Neighborhood of a Vertex3.3.4 Transitivity, Feedback Sets, and Consistent ArcsSmallest Feedback SetsAcyclic Subdigraphs and Transitive Sub-TournamentsArc-Disjoint Cycles3.3.5 Kings, Oriented Trees, and ReachabilityTournaments Containing Oriented TreesArc-Colorings and Monochromatic Paths3.3.6 Domination3.3.7 Tournament Matrices3.3.8 VotingDeciding Who WonTournaments That Are Majority DigraphsAgendasDivision Trees and Sophisticated DecisionsInductively Determining the Sophisticated DecisionReferencesGlossary for Chapter 3Figure 3.1.1Figure 3.1.2Figure 3.1.3Figure 3.1.4Figure 3.1.5Figure 3.1.6Figure 3.1.7Figure 3.1.8Figure 3.1.9Figure 3.1.10Figure 3.1.11Figure 3.1.12Figure 3.2.1Figure 3.2.2Figure 3.2.3Figure 3.2.4Figure 3.2.5Figure 3.2.6Figure 3.2.7Figure 3.2.8Figure 3.2.9Figure 3.2.10Figure 3.2.11Figure 3.2.12Figure 3.2.13Figure 3.2.14Figure 3.3.1Figure 3.3.2Figure 3.3.3Figure 3.3.4Figure 3.3.5Figure 3.3.6Figure 3.3.7Figure 3.3.8Figure 3.3.9Figure 3.3.10
Chapter 4 Connectivity and Traversability
Section 4.1 Connectivity: Properties and Structure4.1.1 Connectivity ParametersPreliminariesVertex- and Edge-ConnectivityRelationships Among the ParametersSome Simple ObservationsInternally-Disjoint Paths and Whitney's TheoremStrong Connectivity in DigraphsAn Application to Interconnection Networks4.1.2 CharacterizationsMenger's TheoremsOther Versions and Generalizations of Menger's TheoremAnother Menger-Type TheoremWhitney's TheoremOther Characterizations4.1.3 Structural ConnectivityCycles Containing Prescribed VerticesThe Lovász—Woodall ConjecturePaths with Prescribed Initial and Final VerticesSubgraphs4.1.4 Analysis and SynthesisContractions and SplittingsSubgraph ContractionEdge DeletionVertex DeletionProducts of GraphsMinimality and CriticalityVertex-Minimal Connectivity — CriticalityConnectivity AugmentationReferencesSection 4.2 Eulerian Graphs4.2.1 Basic Definitions and CharacterizationsSome Basic CharacterizationsCharacterizations Based on Partition Cuts4.2.2 Algorithms to Construct Eulerian ToursThe Splitting and Detachment Operations4.2.3 Eulerian-Tour Enumeration and Other Counting Problems4.2.4 Applications to General GraphsCovering Walks and Double TracingsMaze SearchingCovers, Double Covers, and PackingsThree Optimization ProblemsNowhere-Zero Flows4.2.5 Various Types of Eulerian Tours and Cycle DecompositionsIncidence-Partition and Transition SystemsOrderings of the Incidence Set, Non-Intersecting Tours, and A-Trails4.2.6 Transforming Eulerian ToursThe Kappa TransformationsSplicing the Trails in a Trail DecompositionReferencesSection 4.3 Chinese Postman Problems4.3.1 The Basic Problem and Its VariationsThe Eulerian CaseVariations of CPP4.3.2 Undirected Postman Problems4.3.3 Directed Postman ProblemsProducing an Eulerian Tour in a Symmetric (Multi)Digraph4.3.4 Mixed Postman ProblemsDeciding if a Mixed Graph Is EulerianThe Postman Problem for Mixed GraphsApproximation Algorithm ESApproximate Algorithm SESome Performance Bounds4.3.5 Recent ResearchReferencesSection 4.4 DeBruijn Graphs and Sequences4.4.1 DeBruijn Graph BasicsDeBruijn SequencesDeBruijn Graphs4.4.2 Generating deBruijn SequencesAlgorithmNecklaces and Lyndon Words4.4.3 Pseudorandom Numbers4.4.4 A Genetics ApplicationReferencesSection 4.5 Hamiltonian Graphs4.5.1 History4.5.2 The Classic AttacksDegreesOther CountsPowers and Line GraphsPlanar Graphs4.5.3 Extending the ClassicsAdding ToughnessMore Than Hamiltonian4.5.4 More Than One Hamiltonian CycleA Second Hamiltonian CycleMany Hamiltonian CyclesUniquely Hamiltonian GraphsProducts and Hamiltonian Decompositions4.5.5 Random Graphs4.5.6 Spectral Attacks4.5.7 Forbidden SubgraphsReferencesSection 4.6 Traveling Salesman Problems4.6.1 The Traveling Salesman ProblemSymmetric and Asymmetric TSPMatrix Representation of TSPAlgorithmic ComplexityExact and Approximate AlgorithmsThe Euclidean TSP4.6.2 Exact AlgorithmsInteger Programming Approaches4.6.3 Construction HeuristicsGreedy-Type AlgorithmsInsertion AlgorithmsMinimum Spanning Tree HeuristicsWorst Case Analysis of Heuristics4.6.4 Improvement HeuristicsExponential Neighborhoods4.6.5 The Generalized TSPTransforming Generalized TSP to TSPExact AlgorithmsApproximate Algorithms4.6.6 The Vehicle Routing ProblemExact AlgorithmsHeuristics for CVRPSavings HeuristicsInsertion HeuristicsTwo-phase HeuristicsReferencesSection 4.7 Further Topics in Connectivity4.7.1 High ConnectivityMinimum Degree and DiameterDegree SequenceDistanceSuper Edge-ConnectivityDigraphsOriented GraphsSemigirthLine DigraphsGirthGirth PairCagesLarge DigraphsLarge Graphs4.7.2 Bounded Connectivityπ-SemigirthImbeddingsAdjacency SpectrumLaplacian Spectrum4.7.3 Symmetry and RegularityBoundaries, Fragments, and AtomsFragments and Atoms in Undirected GraphsFragments and Atoms in DigraphsGraphs with SymmetryCayley GraphsCirculant GraphsDistance-Regular Graphs4.7.4 Generalizations of Connectivity ParametersConditional ConnectivityRestricted ConnectivityDistance ConnectivityHigh Distance ConnectivityMaximal ConnectivityHamiltonian ConnectivityReferencesGlossary for Chapter 4Figure 4.1.1Figure 4.1.2Figure 4.2.1Figure 4.2.2Figure 4.2.3Figure 4.2.4Figure 4.2.5Figure 4.2.6Figure 4.2.7Figure 4.2.8Figure 4.2.9Figure 4.2.10Figure 4.3.1Figure 4.3.2Figure 4.3.3Figure 4.3.4Figure 4.3.5Figure 4.3.6Figure 4.3.7Figure 4.3.8Figure 4.3.9Figure 4.4.1Figure 4.4.2Figure 4.4.3Figure 4.5.1Figure 4.5.2Figure 4.5.3Figure 4.6.1Figure 4.6.2Figure 4.6.3Figure 4.6.4Figure 4.6.5Figure 4.6.6Figure 4.7.1Figure 4.7.2Figure 4.7.3Figure 4.7.4Figure 4.7.5Figure 4.7.6

Chapter 5 Colorings and Related Topics
Section 5.1 Graph Coloring5.1.1 General ConceptsProper Vertex-Coloring and Chromatic NumberList Coloring and Choice NumberThe Hajós ConstructionLovász's Topological Lower BoundAlon and Tarsi's Graph Polynomial CharacterizationList Reduction5.1.2 Vertex Degrees5.1.3 Critical Graphs and Uniquely Colorable GraphsUniquely Colorable Graphs5.1.4 Girth and Clique NumberThe Conjectures of Hadwiger and Hajós5.1.5 Edge-Coloring and χ-Binding FunctionsSnarksUniquely Edge-Colorable GraphsFurther χ-Bound Graph Classes5.1.6 Coloring and OrientationPaths and CyclesEulerian SubgraphsChoosability and Orientations with KernelsAcyclic Orientations5.1.7 Colorings of Infinite GraphsColoring Euclidean Spaces and Distance GraphsReferencesSection 5.2 Further Topics in Graph Coloring5.2.1 Multicoloring and Fractional Coloring5.2.2 Graphs on SurfacesHeawood Number and the Empire ProblemNowhere-Zero FlowsChromatic Polynomials5.2.3 Some Further Types of Coloring ProblemsVariants of Proper ColoringGraph HomomorphismsColoring with CostsVertex RankingNon-Repetitive (Thue) ColoringsPartial Colorings and ExtensionsColoring Cubic Graphs with Triple SystemsNeighbor-Distinguishing ColoringsMaximizing the Number of ColorsPartitions with Weaker Requirements5.2.4 Colorings of HypergraphsClique Hypergraphs5.2.5 Algorithmic ComplexityApproximationReferencesSection 5.3 Independence and Cliques5.3.1 Basic Definitions and ApplicationsSome Combinatorial Optimization ProblemsVertex-Weighted GraphsApplications Involving Hamming Distance5.3.2 Integer Programming FormulationsTwo More Formulations of the Maximum-Clique Problem5.3.3 Hardness Results5.3.4 Bounds on Independence and Clique NumbersLower BoundsUpper bounds5.3.5 Exact AlgorithmsClique EnumerationMaximum-Clique and Maximum-Weight-Clique Algorithms5.3.6 HeuristicsConstruction Heuristics and Local SearchTabu SearchReferencesSection 5.4 Factors and Factorization5.4.1 Preliminaries5.4.2 1-FactorsConditions for a Graph to Have a 1-FactorThe Number of 1-Factors: Bounds1-Factors in Bipartite GraphsThe Number of 1-Factors: Exact Counting5.4.3 Degree Factorsk-factorsf-factors[a,b]-factors(g,f)-factorsFactors in Random Graphs5.4.4 Component Factors5.4.5 Graph FactorizationEdge PartitionsVertex PartitionsFactor Algorithms and ComplexitySubgraph ProblemsReferencesSection 5.5 Applications to TimetablingAutomated Timetabling: Historical Perspective5.5.1 Specification of Timetabling ProblemsThe General ProblemTimesResourcesMeetingsConstraints5.5.2 Class-Teacher TimetablingThe Basic Class-Teacher Timetabling ProblemExtensions to the Basic Class-Teacher ProblemGraph Models for Subproblems of the Class-Teacher Problem5.5.3 University Course TimetablingBasic ModelA Graph FormulationScheduling Multi-Section Courses5.5.4 University Examination TimetablingBasic ModelA More Compact ScheduleThe Breadth and Variation of Exam Timetabling ConstraintsHeuristic MethodsTwo Different Random-Selection StrategiesHybrid Graph-Coloring/Meta-Heuristic Approaches5.5.5 Sports TimetablingA Simple Graph ModelProfiles, Breaks, and Home-Away Patterns of a ScheduleA Lower Bound on the Number of BreaksIrreducible and Compact SchedulesComplementarityConstructing a Compact Schedule with a Minimum Number of BreaksAn Alternate View of the Canonical FactorizationSome Characterization ResultsFeasible SequencesReferencesSection 5.6 Graceful Labelings5.6.1 Trees5.6.2 Cycle-Related Graphs5.6.3 Product-Related Graphs5.6.4 Complete Graphs5.6.5 Disconnected Graphs5.6.6 Joins of Graphs5.6.7 α-labelingsReferencesGlossary for Chapter 5Figure 5.3.1Figure 5.5.1Figure 5.5.2Figure 5.5.3Figure 5.5.4Figure 5.5.5Figure 5.5.6Figure 5.5.7Figure 5.5.8Figure 5.5.9Figure 5.5.10Figure 5.5.11Figure 5.5.12
Chapter 6 Algebraic Graph Theory
Section 6.1 Automorphisms6.1.1 The Automorphism Group of a Graph6.1.2 Graphs with Given GroupFurther Reading6.1.3 Groups of Graph ProductsFurther Reading6.1.4 TransitivityFurther Reading6.1.5 s-Regularity and s-Transitivity6.1.6 Graphical Regular Representations6.1.7 Primitivity6.1.8 More Automorphisms of Infinite GraphsStripsAutomorphisms and Distance6.1.9 DistinguishabilityFurther ReadingDistinguishing Number of Graph ProductsMore Distinguishing Number Results for Infinite GraphsReferencesSection 6.2 Cayley Graphs6.2.1 Construction and Recognition6.2.2 Prevalence6.2.3 Isomorphism6.2.4 Subgraphs6.2.5 Factorization6.2.6 MiscellaneousEmbeddingsApplicationsFurther ReadingReferencesSection 6.3 Enumeration6.3.1 Counting Simple Graphs and MultigraphsLabeled GraphsUnlabeled Graphs6.3.2 Counting Digraphs and TournamentsLabeled DigraphsUnlabeled Digraphs6.3.3 Counting Generic Trees6.3.4 Counting Trees in Chemistry6.3.5 Counting Trees in Computer Science ReferencesSection 6.4 Graphs and Vector Spaces6.4.1 Basic Concepts and DefinitionsSubgraphs and ComplementsComponents, Spanning Trees, and Cospanning TreesCuts and CutsetsVector Space of a Graph under Ring Sum of Its Edge Subsets6.4.2 Circuit Subspace of an Undirected GraphFundamental Circuits and the Dimension of the Circuit Subspace6.4.3 Cutset Subspace of an Undirected GraphFundamental Cutsets and the Dimension of the Cutset Subspace6.4.4 Relationship between Circuit and Cutset SubspacesOrthogonality of Circuit and Cutset SubspacesCirc/Cut-Based Decomposition of Graphs and Subgraphs6.4.5 Circuit and Cutset Spaces in a Directed GraphCircuit and Cut Vectors and MatricesFundamental Circuit, Fundamental Cutset, and Incidence MatricesOrthogonality and the Matrix Tree TheoremMinty’s Painting Theorem6.4.6 Two Circ/Cut-Based Tripartitions of a GraphBicycle-Based TripartitionA Tripartition Based on Maximally Distant Spanning Trees6.4.7 Realization of Circuit and Cutset SpacesWhitney and Kuratowski6.4.8 An Application: Cross-Layer Survivability in a Layered NetworkReferencesSection 6.5 Spectral Graph Theory6.5.1 Basic Matrix Properties6.5.2 Walks and the SpectrumWalks and the Coefficients of the Characteristic PolynomialWalks and the Minimal PolynomialRegular Graphs6.5.3 Line Graph, Root System, Eigenvalue BoundsLine Graphs and Generalized Line GraphsRoot SystemsEigenvalue BoundsFurther Reading6.5.4 Distance-Regular GraphsDistance-Regular Graphs and the Hoffman PolynomialStrongly Regular GraphsFurther Reading6.5.5 Spectral CharacterizationEigenvalues and Graph Operations6.5.6 The LaplacianFurther ReadingReferencesSection 6.6 Matroidal Methods in Graph Theory6.6.1 Matroids: Basic Definitions and Examples6.6.2 Alternative Axiom Systems6.6.3 The Greedy Algorithm6.6.4 Duality6.6.5 Matroid Union and Its Consequences6.6.6 Fundamental Operations6.6.7 Connectedness, 2- and 3-Connectedness for Graphs and MatroidsBounds on the number of elements2-sums and 3-sums6.6.8 Graphs and Totally Unimodular Matrices6.6.9 Excluded-Minor Characterizations6.6.10 Wheels, Whirls, and the Splitter Theorem6.6.11 Removable Circuits6.6.12 Minimally k-connected Graphs and Matroids6.6.13 ConclusionReferencesGlossary for Chapter 6Figure 6.1.1Figure 6.1.2Figure 6.2.1Figure 6.2.2Figure 6.3.1Figure 6.3.2Figure 6.3.3Figure 6.3.4Figure 6.3.5Figure 6.3.6Figure 6.3.7Figure 6.3.8Figure 6.3.9Figure 6.4.1Figure 6.4.2Figure 6.4.3Figure 6.4.4Figure 6.4.5Figure 6.4.6Figure 6.4.7Figure 6.4.8Figure 6.4.9Figure 6.4.10Figure 6.4.11Figure 6.5.1Figure 6.5.2Figure 6.5.3Figure 6.5.4Figure 6.5.5Figure 6.5.6Figure 6.6.1Figure 6.6.2Figure 6.6.3Figure 6.6.4Figure 6.6.5Figure 6.6.6Figure 6.6.7Figure 6.6.8Table 6.3.1Table 6.3.2Table 6.3.3Table 6.3.4Table 6.3.5Table 6.3.6Table 6.3.7Table 6.3.8Table 6.3.9Table 6.3.10Table 6.3.11Table 6.3.12Table 6.3.13Table 6.3.14Table 6.6.1Table 6.6.2Table 6.6.3Table 6.6.4Table 6.6.5Table 6.6.6
Chapter 7 Topological Graph Theory
Section 7.1 Graphs on Surfaces7.1.1 Surfaces2-Manifolds and 2-PseudomanifoldsSome Standard SurfacesSurface Operations and Classification7.1.2 Polygonal Complexes7.1.3 Imbeddings7.1.4 Combinatorial Descriptions of MapsAlgorithmReferencesSection 7.2 Minimum Genus and Maximum Genus7.2.1 Definitions and Basic FactsEar DecompositionEdge Insertion and Deletion7.2.2 Kuratowski-Type TheoremsMinimum GenusMaximum Genus7.2.3 Planarity and Upper-Embeddability7.2.4 Lower BoundsLower Bounds on Minimum GenusLower Bounds on Maximum Genus7.2.5 Algorithmic IssuesMinimum Genus AlgorithmsMaximum Genus AlgorithmsReferencesSection 7.3 Genus Distributions7.3.1 Ranges and Distributions of Imbeddings7.3.2 Counting Noncellular Imbeddings7.3.3 Partitioned Genus Distributions7.3.4 Graph AmalgamationsBar AmalgamationsVertex Amalgamations7.3.5 Genus Distribution Formulas for Special Classes7.3.6 Other Imbedding Distribution Calculations7.3.7 The Unimodality Problem7.3.8 Average Genus7.3.9 Stratification of ImbeddingsReferencesSection 7.4 Voltage Graphs7.4.1 Regular Voltage GraphsFibersBouquets and DipolesNet Voltages7.4.2 Local Group and Natural AutomorphismsThe Local GroupNatural Automorphisms7.4.3 Permutation Voltage Graphs7.4.4 Representing Coverings with Voltage GraphsCoverings and Branched Coverings of SurfacesUsing Voltage Graph ConstructionsAction of the Group of Covering Transformations7.4.5 The Kirchhoff Voltage Law7.4.6 Imbedded Voltage Graphs7.4.7 Topological Current Graphs7.4.8 Lifting Voltage Graph Mappings7.4.9 Applications of Voltage GraphsApplications of Imbedded Voltage Graphs and Topological Current GraphsReferencesSection 7.5 The Genus of a Group7.5.1 Symmetric Imbeddings of Cayley Graphs7.5.2 Riemann—Hurwitz Equation; Hurwitz’s Theorem7.5.3 Groups of Low Genus7.5.4 Genus for Families of Groups7.5.5 Non-Orientable SurfacesReferencesSection 7.6 Maps7.6.1 Maps and Polyhedral Maps7.6.2 Existence and Realizations of Polyhedral Maps7.6.3 Paths and Cycles in Maps7.6.4 Map Coloring7.6.5 Combinatorial Schemes7.6.6 Maps and Universal Tessellations7.6.7 Highly Symmetrical Maps7.6.8 Enumeration of MapsReferencesSection 7.7 Representativity7.7.1 Basic Concepts7.7.2 Coloring Densely Imbeddable GraphsColoring with Few ColorsColoring Graphs that QuadrangulateColoring Graphs That Triangulate7.7.3 Finding Cycles, Walks, and Spanning Trees7.7.4 Re-Imbedding PropertiesLEW-ImbeddingsImbeddings and ConnectivityImbeddings and GenusRe-Imbedding Results7.7.5 Minors of Imbedded GraphsSurface MinorsFinding Imbedded Cycles7.7.6 Minor-Minimal MapsSimilarity Classes on the TorusKernelsReferencesSection 7.8 Triangulations7.8.1 Basic ConceptsNotations7.8.2 Constructing TriangulationsTriangulations with Complete GraphsMinimum TriangulationsCovering Constructions7.8.3 Irreducible TriangulationsEdge ContractionClassification and Finiteness in NumberOther Irreducibility7.8.4 Diagonal FlipsEstimating BoundsCatalan TriangulationsPreserving Properties7.8.5 Rigidity and FlexibilityEquivalence over ImbeddingsUniqueness of ImbeddingsRe-Imbedding StructuresImbeddings into Other SurfacesReferencesSection 7.9 Graphs and Finite Geometries7.9.1 Finite Geometries7.9.2 Associated Graphs7.9.3 Surface ModelsReferencesSection 7.10 Crossing Numbers7.10.1 Drawings of Graphs and Crossing NumbersEmbeddingsDrawingsCrossing Numbers7.10.2 General Techniques and BoundsThe Crossing LemmaCrossing Numbers, Bisection Width, and CutwidthCrossing Numbers, Immersion, and Congestion7.10.3 Crossing Numbers of Some Families of GraphsComplete Bipartite GraphsComplete GraphsOther Families of Graphs7.10.4 Crossing-Critical Graphs7.10.5 Algorithmical Aspects7.10.6 Other Definitions of Crossing Number7.10.7 Crossing Sequences7.10.8 Applications of Crossing Numbers7.10.9 Suggestions for Further ReadingReferencesGlossary for Chapter 7Figure 7.1.1Figure 7.1.2Figure 7.1.3Figure 7.1.4Figure 7.1.5Figure 7.1.6Figure 7.1.7Figure 7.1.8Figure 7.1.9Figure 7.1.10Figure 7.1.11Figure 7.1.12Figure 7.1.13Figure 7.2.1Figure 7.2.2Figure 7.2.3Figure 7.3.1Figure 7.3.2Figure 7.3.3Figure 7.3.4Figure 7.3.5Figure 7.3.6Figure 7.3.7Figure 7.3.8Figure 7.3.9Figure 7.3.10Figure 7.3.11Figure 7.3.12Figure 7.3.13Figure 7.3.14Figure 7.3.15Figure 7.3.16Figure 7.4.1Figure 7.4.2Figure 7.4.3Figure 7.4.4Figure 7.4.5Figure 7.4.6Figure 7.4.7Figure 7.4.8Figure 7.6.1Figure 7.6.2Figure 7.6.3Figure 7.6.4Figure 7.6.5Figure 7.6.6Figure 7.6.7Figure 7.6.8Figure 7.6.9Figure 7.6.10Figure 7.6.11Figure 7.6.12Figure 7.6.13Figure 7.6.14Figure 7.6.15Figure 7.6.16Figure 7.6.17Figure 7.6.18Figure 7.6.19Figure 7.7.1Figure 7.7.2Figure 7.7.3Figure 7.8.1Figure 7.8.2Figure 7.8.3Figure 7.8.4Figure 7.8.5Figure 7.8.6Figure 7.8.7Figure 7.8.8Figure 7.8.9Figure 7.8.10Figure 7.8.11Figure 7.8.12Figure 7.8.13Figure 7.9.1Figure 7.9.2Figure 7.9.3Figure 7.9.4Figure 7.9.5Figure 7.10.1Figure 7.10.2Figure 7.10.3Table 7.1
Chapter 8 Analytic Graph Theory
Section 8.1 Extremal Graph Theory8.1.1 Turán-Type ProblemsTurán's Theorem and Its ExtensionsStructural Properties of the Graphs G(n, tr(n) + 1)Books and Generalized BooksVertex-Disjoint Cliques8.1.2 The Number of Complete Graphs8.1.3 Erdős–Stone Theorem and Its ExtensionsThe Structure of Extremal Graphs8.1.4 Zarankiewicz Problem and Related Questionsκr-Free Graphs with Large Minimal Degree8.1.5 Paths and Trees8.1.6 Circumference8.1.7 Hamiltonian Cycles8.1.8 Cycle LengthsCycles of Consecutive LengthsPancyclicity and Weak Pancyclicity8.1.9 Szemerédi's Uniformity LemmaApplications of the Uniformity and Blow-up lemmas8.1.10 Asymptotic Enumeration8.1.11 Graph Minors8.1.12 Ramsey–Turán ProblemsReferencesSection 8.2 Random Graphs8.2.1 Random Graph ModelsAsymptotics8.2.2 Threshold Functions8.2.3 Small Subgraphs and the Degree Sequence8.2.4 Phase Transition8.2.5 Many More Properties of Random Graphs8.2.6 Random Regular Graphs8.2.7 Other Random Graph Models8.2.8 Random Graph ProcessesReferencesSection 8.3 Ramsey Graph Theory8.3.1 Ramsey’s TheoremRamsey Numbers for Arbitrary Graphs8.3.2 Fundamental Results8.3.3 Classical Ramsey NumbersRamsey Numbers for Small GraphsAsymptotic Results8.3.4 Generalized Ramsey NumbersInitial Generalized Ramsey ResultsRamsey Numbers for TreesCycle Ramsey NumbersGood ResultsSmall Order GraphsLinear Bounds8.3.5 Size Ramsey NumbersGeneral BoundsLinear BoundsBipartite GraphsSmall Order Graphs8.3.6 Ramsey Minimal Graphs8.3.7 Generalizations and VariationsGraphsHypergraphsReferencesSection 8.4 The Probabilistic Method8.4.1 The First Moment MethodRamsey Numbers8.4.2 Alterations8.4.3 The Lovász Local Lemma8.4.4 The Rödl Nibble8.4.5 Bounds on Tails of Distributions8.4.6 Dependent Random ChoiceReferencesSection 8.5 Graph Limits8.5.1 Graphs, Weighted Graphs, and Graphons8.5.2 Homomorphism Density8.5.3 Convergent Sequences of Graphs and Graphons8.5.4 Metric Space Topology on Graphs and Graphons8.5.5 Regularity Lemma and Approximation of Graphons by Weighted Graphs8.5.6 W-Random Graphs8.5.7 Graph Parameters and Connection Matrices8.5.8 Extremal Graph Theory and the Algebra of Quantum GraphsReferencesGlossary for Chapter 8Figure 8.2.1Figure 8.2.2Figure 8.3.1Figure 8.3.2Figure 8.3.3Figure 8.3.4Figure 8.3.5Figure 8.3.6Figure 8.5.1Figure 8.5.2
Chapter 9 Graphical Measurement
Section 9.1 Distance in Graphs9.1.1 Standard Distance in GraphsDistance and EccentricityRadius and DiameterCenter and PeripherySelf-Centered Graphs9.1.2 Geodetic ParametersGeodetic Sets and Geodetic NumbersConvex Sets and Hull Sets9.1.3 Total Distance and Medians of GraphsTotal Distance of a VertexThe Median of a Connected GraphCenters and Medians of a Connected Graph9.1.4 Steiner Distance in GraphsSteiner Radius and Steiner DiameterSteiner Centers9.1.5 Distance in DigraphsRadius and Diameter in Strong DigraphsThe Center of a Strong DigraphStrong Distance in Strong DigraphsStrong Centers of Strong DigraphsReferencesSection 9.2 Domination in Graphs9.2.1 Dominating Sets in GraphsEquivalent Definitions of a Dominating SetApplications of Domination9.2.2 Minimality ConditionsThe Domination Chain9.2.3 Domination Perfect Graphs9.2.4 Bounds on the Domination NumberBounds in Terms of Order and Minimum DegreeMinimum Degree TwoMinimum Degree ThreeCubic GraphsMore Bounds Involving Minimum DegreeBounds in Terms of Size and DegreeBounds in Terms of Order and Maximum DegreeBounds in Terms of Order and SizeBounds in Terms of PackingBounds in Terms of Radius9.2.5 Nordhaus-Gaddum-Type Results9.2.6 Domination in Planar Graphs9.2.7 Vizing's Conjecture9.2.8 Domination Critical Graphs9.2.9 Domination ParametersReferencesSection 9.3 Tolerance Graphs9.3.1 Intersection Graphs and Their ApplicationsContainment Graphs9.3.2 The Classical Model of Interval Tolerance9.3.3 The Algorithmics of Tolerance Graphs9.3.4 Variations of Tolerance on Intervalsɸ-Tolerance GraphsThreshold Tolerance and coTT GraphsBounded Bitolerance Graphs and Ordered Sets9.3.5 Rank-Tolerance GraphsBackground9.3.6 Intersection and Tolerance Graphs on TreesThe (h, s, t) Graphs: Degree Constrained RepresentationsReferencesSection 9.4 Bandwidth9.4.1 FundamentalsThe Bandwidth ConceptApplicationsEfficient Matrix StorageVLSI LayoutInterconnection NetworksBinary Constraint Satisfaction ProblemAlgorithms9.4.2 Elementary ResultsThe Bandwidth of Some Common Families of GraphsA Few Basic RelationsOn the Bandwidth of TreesAlternative Interpretations of Bandwidth9.4.3 Bounds on BandwidthTwo General BoundsSubdivisions, Mergers, Contractions, and Edge AdditionsNordhaus-Gaddum Types of BoundsOther Bounds9.4.4 On the Bandwidth of Combinations of GraphsCartesian ProductSum of Two GraphsCorona and CompositionStrong Product and Tensor Product9.4.5 Bandwidth and Its Relationship to Other InvariantsVertex DegreeNumber of Vertices and Edges for Arbitrary GraphsNumber of Vertices and Edges for Graphs with no κ3Radius and DiameterVertex and Edge Chromatic NumberVertex Independence and Vertex Cover NumbersGirth, Vertex Arboricity, and Thickness9.4.6 Related ConceptsBandsizeEdgesum (Bandwidth Sum)Cyclic BandwidthEdge-BandwidthProfileCutwidthTopological BandwidthAdditive BandwidthReferencesSection 9.5 Pursuit-Evasion Problems9.5.1 Sweeping and Edge Search9.5.2 Node Search and Mixed Search9.5.3 Cops-and-Robbers9.5.4 Additional VariationsReferencesGlossary for Chapter 9Figure 9.1.1Figure 9.1.2Figure 9.1.3Figure 9.1.4Figure 9.1.5Figure 9.1.6Figure 9.1.7Figure 9.1.8Figure 9.1.9Figure 9.1.10Figure 9.1.11Figure 9.1.12Figure 9.1.13Figure 9.1.14Figure 9.1.15Figure 9.1.16Figure 9.1.17Figure 9.2.1Figure 9.2.2Figure 9.2.3Figure 9.2.4Figure 9.2.5Figure 9.2.6Figure 9.2.7Figure 9.2.8Figure 9.2.9Figure 9.2.10Figure 9.2.11Figure 9.2.12Figure 9.4.1Figure 9.4.2Figure 9.4.3Figure 9.4.4Figure 9.4.5Figure 9.4.6Figure 9.4.7Figure 9.4.8Figure 9.4.9Figure 9.4.10Figure 9.5.1Figure 9.5.2Figure 9.5.3Figure 9.5.4Figure 9.5.5Figure 9.5.6Figure 9.5.7Figure 9.5.8Table 9.1
Chapter 10 Graphs in Computer Science
Section 10.1 Searching10.1.1 Breadth-First SearchOrdered Trees10.1.2 Depth-First SearchDiscovery Order10.1.3 Topological Order10.1.4 Connectivity PropertiesStrong Components of a Directed GraphBridges and Cutpoints of an Undirected Graph10.1.5 DFS as a Proof Technique10.1.6 More Graph PropertiesPlanarity TestingTriconnectivityEar Decomposition and st-numberingReducibilityTwo Directed Spanning TreesDominatorsFacts About Semidominators10.1.7 Approximation AlgorithmsAlgorithmReferencesSection 10.2 Dynamic Graph Algorithms10.2.1 Basic Terminology10.2.2 Dynamic Problems on Undirected GraphsGeneral Techniques for Undirected GraphsTopology TreesAssumptionApproachET TreesApproachTop TreesApproachClusteringSparsificationApproachNotationRandomizationApproachConnectivityInvariantsMinimum Spanning TreesDecremental Minimum Spanning TreeApproachInvariantFully Dynamic Minimum Spanning Tree10.2.3 Dynamic Problems on Directed GraphsGeneral Techniques for Directed GraphsPath Problems and Kleene ClosuresLocally Shortest PathsLong Paths PropertyReachability TreesMatrix Data StructuresDynamic Transitive ClosureKing's O(n2 log n) Update AlgorithmApproachDemetrescu and Italiano's O(n2) Update AlgorithmApproachNotationDynamic Shortest PathsNotationKing's On2.5 C log n Update AlgorithmApproachDemetrescu and Italiano's O(n2 log3 n) Update AlgorithmApproach10.2.4 Research IssuesFurther InformationAcknowledgmentsReferencesSection 10.3 Drawings of Graphs10.3.1 Types of Graphs and DrawingsTypes of GraphsTypes of Drawings10.3.2 Combinatorics of Some Geometric GraphsDelaunay Triangulationsβ-drawings and Rectangle of Influence DrawingsMinimum Spanning TreesMinimum Weight Triangulations10.3.3 Properties of Drawings and BoundsProperties of DrawingsBounds on the AreaBounds on the Angular ResolutionBounds on the Number of BendsTradeoff Between Area and Aspect RatioTradeoff between Area and Angular Resolution10.3.4 Complexity of Graph Drawing Problems10.3.5 Example of a Graph Drawing Algorithm10.3.6 Techniques for Drawing GraphsPlanarizationLayeringPhysical Simulation10.3.7 Selected TopicsPoint-Set Embeddings and Universal Point SetsSimultaneous EmbeddingsLombardi DrawingsDrawings with Large Crossing AnglesDrawings with Few SlopesWitness Proximity and Approximate Proximity DrawingsCluster Planarity10.3.8 Sources and Related MaterialReferencesSection 10.4 Algorithms on Recursively Constructed GraphsAlgorithm Design Strategy10.4.1 Algorithms on TreesMaximum-Cardinality Independent Set in a TreeMaximum-Weight Independent Set in a Tree10.4.2 Algorithms on Series-Parallel GraphsMaximum-Cardinality Independent Set in a Series-Parallel GraphMultiplication Tables for Series, Parallel, and Jacknife Operations10.4.3 Algorithms on Treewidth-k GraphsMaximum-Cardinality Independent Set in a Treewidth-k GraphMonadic Second-Order Logic Expressions for a GraphMSOL-Expressible Graph Problems10.4.4 Algorithms on CographsThree More Algorithms for Cographs10.4.5 Algorithms on Cliquewidth-k GraphsMaximum-Cardinality Independent Set of a Cliquewidth-k GraphA Subset of the MSOL Expressions for a Graph10.4.6 Algorithms on k-HB GraphsMaximum-Cardinality Independent Set in a k-HB GraphA Subset of the MSOL' ExpressionsReferencesSection 10.5 Fuzzy Graphs10.5.1 Definitions and Basic Properties10.5.2 Paths and Connectedness10.5.3 Forests and Trees10.5.4 Fuzzy Cut Sets10.5.5 Fuzzy 1-Chain with Boundary 0, Fuzzy Coboundary, and Fuzzy Cocycles10.5.6 Fuzzy Line Graphs10.5.7 Fuzzy Interval Graphs10.5.8 Operations on Fuzzy Graphs10.5.9 Clusters10.5.10 Application to Cluster Analysis10.5.11 Fuzzy Graphs in Database Theory10.5.12 Strengthening and Weakening Members of a Group10.5.13 Network Analysis of Fuzzy Graphs10.5.14 Intuitionistic Fuzzy Graphs and Group Decision-MakingReferencesSection 10.6 Expander Graphs10.6.1 Foundational Definitions and ResultsIsoperimetric Constants and Expander FamiliesRelationship to Graph SpectraRamanujan Graphs and the Alon–Boppana TheoremGroup Representations and Kazhdan Constants10.6.2 Major Results and Open ProblemsExistence and Construction of Expander FamiliesRamanujan Graphs and Zeta FunctionsGroup Structure and ExpansionRandom Graphs and Expansion Definitions10.6.3 Other Surveys and General SourcesReferencesSection 10.7 Visibility Graphs10.7.1 Bar-Visibility Graphs10.7.2 Rectangle-Visibility Graphs10.7.3 Visibility Representations in ℝ310.7.4 Box-Visibility Graphs10.7.5 Bar k-Visibility Graphs10.7.6 Bar Visibility Number10.7.7 Other Visibility GraphsReferencesGlossary for Chapter 10Figure 10.1.1Figure 10.1.2Figure 10.1.3Figure 10.1.4Figure 10.1.5Figure 10.1.6Figure 10.1.7Figure 10.1.8Figure 10.1.9Figure 10.1.10Figure 10.1.11Figure 10.1.12Figure 10.1.13Figure 10.1.14Figure 10.1.15Figure 10.1.16Figure 10.1.17Figure 10.1.18Figure 10.1.19Figure 10.1.20Figure 10.1.21Figure 10.1.22Figure 10.1.23Figure 10.1.24Figure 10.2.1Figure 10.2.2Figure 10.2.3Figure 10.2.4Figure 10.3.1Figure 10.3.2Figure 10.3.3Figure 10.4.1Figure 10.4.2Figure 10.4.3Figure 10.4.4Figure 10.4.5Figure 10.4.6Figure 10.6.1Figure 10.6.2Figure 10.7.1Figure 10.7.2Figure 10.7.3Figure 10.7.4Figure 10.7.5Figure 10.7.6Figure 10.7.7Figure 10.7.8
Chapter 11 Networks and Flows
Section 11.1 Maximum Flows11.1.1 The Basic Maximum Flow Problem11.1.2 Minimum Cuts and DualityCuts in a NetworkWeak Duality11.1.3 Max-Flow Min-Cut TheoremThe Residual Network and Flow-Augmenting Paths11.1.4 Algorithms for Maximum FlowFord–Fulkerson AlgorithmPreflow-Push Algorithms11.1.5 Variants and Extensions of Maximum FlowMulticommodity FlowVariants of Multicommodity Flow ProblemsReferencesSection 11.2 Minimum Cost Flows11.2.1 The Basic Model and DefinitionsResidual Networks11.2.2 Optimality ConditionsA Basic Cycle-Canceling Algorithm11.2.3 The Dual Problem11.2.4 Algorithms for Minimum Cost FlowA Transshipment Problem Associated with a Minimum Cost Flow ProblemA Primal-Dual AlgorithmA Push-Relabel AlgorithmStrongly Polynomial Algorithms11.2.5 Extensions to Minimum Cost FlowConvex Cost FlowsFlows Over TimeFlows with Losses and GainsReferencesSection 11.3 Matchings and Assignments11.3.1 MatchingsBasic TerminologySome Fundamental Results11.3.2 Matchings in Bipartite GraphsBipartite Maximum-Size Matching AlgorithmBipartite Maximum-Weight Matching Algorithm11.3.3 Matchings in Nonbipartite Graphs11.3.4 Stable MatchingsGale–Shapley AlgorithmReferencesSection 11.4 Graph Pebbling11.4.1 SolvabilityNOTATIONWeight FunctionsComplexity11.4.2 Pebbling NumbersDiameter, Connectivity, and Class 0Complexity11.4.3 Optimal PebblingComplexity11.4.4 ThresholdsNOTATION11.4.5 Other VariationsNOTATION11.4.6 ApplicationsReferencesGlossary for Chapter 11Figure 11.1.1Figure 11.1.2Figure 11.1.3Figure 11.1.4Figure 11.1.5Figure 11.1.6Figure 11.1.7Figure 11.2.1Figure 11.2.2Figure 11.2.3Figure 11.2.4Figure 11.3.1Figure 11.3.2Figure 11.3.3Figure 11.3.4Figure 11.3.5Figure 11.3.6Figure 11.3.7Figure 11.3.8Figure 11.3.9Figure 11.3.10Figure 11.3.11Figure 11.3.12Figure 11.4.1Figure 11.4.2Figure 11.4.3Figure 11.4.4Figure 11.4.5Figure 11.4.6Figure 11.4.7Figure 11.4.8Figure 11.4.9
Chapter 12 Communication Networks
Section 12.1 Complex Networks12.1.1 Examples of Complex Networks12.1.2 Properties of Complex Networks12.1.3 Random Graphs with General Degree Distributions12.1.4 On-Line Models of Complex NetworksPreferential Attachment ModelThe Copying ModelIterated Local Transitivity Model12.1.5 Geometric Models for Complex Networks12.1.6 Percolation in a General Host Graph12.1.7 PageRank for Ranking Nodes12.1.8 Network GamesReferencesSection 12.2 Broadcasting and Gossiping12.2.1 BroadcastingMinimum Broadcast TreesB(n) and Minimum Broadcast GraphsConstruction of Sparse Broadcast GraphsBounded Degree Broadcast Graphs12.2.2 GossipingOptimal Gossip GraphsMinimum Gossip Graphs12.2.3 Other Variations of Broadcasting and GossipingReferencesSection 12.3 Communication Network Design Models 149512.3.1 General Network Design ModelPreliminariesSUMMARY OF NOTATIONGeneral Edge-Based Flow ModelGeneral Model: Edge-Flow [GM:EF]General Path-Flow ModelGeneral Model: Path-Flow [GM:PF]12.3.2 Uncapacitated Network DesignUncapacitated Network Design [UND]ASSUMPTIONSMulti-Level Network DesignMulti-Level Network Design Model [MLND]MLND Composite Heuristic12.3.3 Survivable Network Design (SND)Uncapacitated Survivable Network Design [SNDUnc]Cut-Based Formulation of SND [SND-CUT]SND Iterative Rounding HeuristicFlow-Based Formulation of SND [SND-FLOW]Survivable Network Design: Bounded Cycles12.3.4 Capacitated Network DesignNetwork Loading Problem [NLP]Capacitated Concentrator Location [CCL]Capacitated Concentrator Location Model [CCL]Survivable Network Design (Capacitated)Diversification and Reservation Model [DR]p-Cycle Protection Model [PP]ReferencesSection 12.4 Network Science for Graph Theorists12.4.1 Network Measures and PropertiesStructural Measures: Centrality12.4.2 Other Structural MeasuresReciprocity on DyadsTransitivity on TriadsBalance on TriadsCommunities and Partitions12.4.3 Attribute or Data MeasuresSimilarityHomophily12.4.4 Process Measures12.4.5 Modeling with Networks12.4.6 Process Dynamics12.4.7 Structural Classification12.4.8 Future DirectionsReferencesGlossary for Chapter 12Figure 12.2.1Figure 12.2.2Figure 12.2.3Figure 12.2.4Figure 12.2.5Figure 12.2.6Figure 12.2.7Figure 12.2.8Figure 12.3.1Figure 12.3.2Figure 12.3.3Figure 12.3.4Figure 12.3.5Figure 12.3.6Figure 12.4.1Figure 12.4.2Figure 12.4.3Figure 12.4.4Figure 12.4.5Table 12.1Table 12.2Table 12.3
Chapter 13 Natural Science & Processes
Section 13.1 Chemical Graph Theory13.1.1 Basic Definitions13.1.2 Molecular Energy13.1.3 Graph Nullity and Zero-Energy States13.1.4 Graph-Based Molecular Descriptors13.1.5 Walk-Based Molecular Parameters13.1.6 Vibrational Analysis of GraphsReferencesSection 13.2 Ties between Graph Theory and Biology13.2.1 Biological Primer13.2.2 Graphs in Sequencing and MappingInterval Graphs in DNA MappingAdjoint Graphs in DNA SequencingQuasi-Adjoint Graphs in DNA SequencingLabeled Graphs in DNA Assembling13.2.3 Probabilistics and GraphsGraphical Models of TF BindingLearning Graphical Models13.2.4 Hypergraphs in BiologyAcknowledgmentsReferencesGlossary for Chapter 13Figure 13.2.1Figure 13.2.2Figure 13.2.3Figure 13.2.4Figure 13.2.5Figure 13.2.6Figure 13.2.7Figure 13.2.8Figure 13.2.9Figure 13.2.10Figure 13.2.11Figure 13.2.12

Content preview from Handbook of Graph Theory, 2nd Edition

Chapter 10

Graphs in Computer Science

Section 10.1 Searching

Harold N. Gabow

University of Colorado

Introduction

A search of a graph is a methodical exploration of all the vertices and edges. It must run in “linear time,” i.e., in one pass (or a small number of passes) over the graph. Even with this restriction, a surprisingly large number of fundamental graph properties can be tested and identified.

This section examines the two most important search methods. Breadth-first search gives an efficient way to compute distances. Depth-first search is useful for checking many basic connectivity properties, for checking planarity, and also for data flow analysis for compilers. A treatment of at least some aspects of both these methods can be found ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

Publisher Resources

ISBN: 9781439880197

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Handbook of Graph Theory, 2nd Edition

by Jonathan L. Gross, Jay Yellen, Ping Zhang

Graphs in Computer Science

Section 10.1 Searching

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.