Handbook of graph theory

Handbook of Graph Theory......Page 1
PREFACE......Page 5
About the Editors......Page 8
CONTRIBUTORS......Page 9
CONTENTS......Page 11
INTRODUCTION TO GRAPHS......Page 14
Contents......Page 0
1.1.1 Graphs and Digraphs......Page 15
1.1.2 Degree and Distance......Page 20
1.1.3 Basic Structural Concepts......Page 23
1.1.4 Trees......Page 28
References......Page 31
1.2.1 Building Blocks......Page 33
1.2.2 Symmetry......Page 34
1.2.3 Integer-Valued Invariants......Page 36
1.2.4 Criterion Qualification......Page 39
References......Page 41
1.3.1 Traversability......Page 42
1.3.2 Trees......Page 46
1.3.3 Topological Graphs......Page 48
1.3.4 Graph Colorings......Page 52
1.3.5 Graph Algorithms......Page 55
References......Page 56
GLOSSARY FOR CHAPTER 1......Page 63
GRAPH REPRESENTATION......Page 69
2.1.1 The Basic Representations for Graphs......Page 70
2.1.2 Graph Traversal Algorithms......Page 72
2.1.3 All-Pairs Problems......Page 75
2.1.4 Applications to Pattern Matching......Page 77
References......Page 80
2.2.1 Variations of the Problem......Page 81
2.2.2 Refinement Technique......Page 82
2.2.3 Practical Graph Isomorphism......Page 85
2.2.4 Group-Theoretic Approach......Page 86
2.2.5 Complexity......Page 87
References......Page 88
2.3.1 Two Reconstruction Conjectures......Page 92
2.3.2 Reconstructible Parameters and Classes......Page 95
2.3.3 Reconstructing from a Partial Deck......Page 97
2.3.4 TutteÌs and KocayÌs Results......Page 101
2.3.5 Lov szÌs Method; Nash-WilliamsÌs Lemma......Page 103
2.3.6 Digraphs......Page 105
References......Page 106
2.4.1 Some Parameterized Families of Graph Classes......Page 112
2.4.2 Equivalences and Characterizations......Page 123
2.4.3 Recognition......Page 125
References......Page 127
GLOSSARY FOR CHAPTER 2......Page 132
DIRECTED GRAPHS......Page 139
3.1.1 Terminology and Basic Facts......Page 140
3.1.2 A Sampler of Digraph Models......Page 145
3.1.3 Binary Trees......Page 152
References......Page 154
3.2.1 Examples and Basic Facts......Page 155
3.2.2 Rooted Trees......Page 158
3.2.3 DAGs and Posets......Page 162
3.2.4 Topological Sort and Optimization......Page 163
References......Page 168
3.3.1 Basic Definitions and Examples......Page 169
3.3.2 Paths, Cycles, and Connectivity......Page 173
3.3.3 Scores and Score Sequences......Page 177
3.3.4 Transitivity, Feedback Sets, Consistent Arcs......Page 179
3.3.5 Kings, Oriented Trees, and Reachability......Page 181
3.3.6 Domination......Page 184
3.3.7 Tournament Matrices......Page 185
3.3.8 Voting......Page 186
References......Page 190
GLOSSARY FOR CHAPTER 3......Page 198
CONNECTIVITY and TRAVERSABILITY......Page 206
4.1.1 Connectivity Parameters......Page 207
4.1.2 Characterizations......Page 211
4.1.3 Structural Connectivity......Page 214
4.1.4 Analysis and Synthesis......Page 216
References......Page 221
4.2.1 Basic Definitions and Characterizations......Page 227
4.2.2 Algorithms to Construct Eulerian Tours......Page 230
4.2.3 Eulerian-Tour Enumeration and Other Counting Problems......Page 233
4.2.4 Applications to General Graphs......Page 235
4.2.5 Various Types of Eulerian Tours and Cycle Decompositions......Page 239
4.2.6 Transforming Eulerian Tours......Page 244
References......Page 246
4.3.1 The Basic Problem and Its Variations......Page 250
4.3.2 Undirected Postman Problems......Page 252
4.3.3 Directed Postman Problems......Page 254
4.3.4 Mixed Postman Problems......Page 256
References......Page 264
4.4.1 DeBruijn Graph Basics......Page 266
4.4.2 Generating deBruijn Sequences......Page 268
4.4.3 Pseudorandom Numbers......Page 271
4.4.4 A Genetics Application......Page 272
References......Page 273
4.5.2 The Classic Attacks......Page 274
4.5.3 Extending the Classics......Page 278
4.5.4 More Than One Hamiltonian Cycle?......Page 280
4.5.5 Random Graphs......Page 283
4.5.6 Forbidden Subgraphs......Page 284
References......Page 286
4.6.1 The Traveling Salesman Problem......Page 292
4.6.2 Exact Algorithms......Page 295
4.6.3 Construction Heuristics......Page 297
4.6.4 Improvement Heuristics......Page 301
4.6.5 The Generalized TSP......Page 302
4.6.6 The Vehicle Routing Problem......Page 304
References......Page 308
4.7.1 High Connectivity......Page 313
4.7.2 Bounded Connectivity......Page 325
4.7.3 Symmetry and Regularity......Page 327
4.7.4 Generalizations of the Connectivity Parameters......Page 333
References......Page 337
GLOSSARY FOR CHAPTER 4......Page 343
COLORINGS and RELATED TOPICS......Page 353
5.1.1 General Concepts......Page 354
5.1.2 Vertex Degrees......Page 358
5.1.3 Critical Graphs and Uniquely Colorable Graphs......Page 359
5.1.4 Girth and Clique Number......Page 361
5.1.5 Edge-Coloring and x-Binding Functions......Page 364
5.1.6 Coloring and Orientation......Page 368
5.1.7 Colorings of Infinite Graphs......Page 370
References......Page 371
5.2.1 Multicoloring and Fractional Coloring......Page 378
5.2.2 Graphs on Surfaces......Page 380
5.2.3 Some Further Types of Coloring Problems......Page 383
5.2.4 Colorings of Hypergraphs......Page 387
5.2.5 Algorithmic Complexity......Page 390
References......Page 393
5.3.1 Basic Definitions and Applications......Page 402
5.3.2 Integer Programming Formulations......Page 404
5.3.3 Complexity and Approximation......Page 406
5.3.4 Bounds on Independence and Clique Numbers......Page 407
5.3.5 Exact Algorithms......Page 408
5.3.6 Heuristics......Page 410
References......Page 411
5.4.1 Preliminaries......Page 416
5.4.2 1-Factors......Page 417
5.4.3 Degree Factors......Page 421
5.4.5 Graph Factorization......Page 426
References......Page 432
5.5.1 Cliques and Independent Sets......Page 444
5.5.2 Graph Perfection......Page 446
5.5.3 Motivating Applications......Page 447
5.5.4 Matrix Representation of Graph Perfection......Page 449
5.5.5 Efficient Computation of Graph Parameters......Page 450
5.5.6 Classes of Perfect Graphs......Page 451
5.5.7 The Strong Perfect Graph Theorem......Page 454
References......Page 455
Introduction......Page 458
5.6.1 Specification of Timetabling Problems......Page 459
5.6.2 Class-Teacher Timetabling......Page 462
5.6.3 University Course Timetabling......Page 465
5.6.4 University Examination Timetabling......Page 470
5.6.5 Sports Timetabling......Page 475
References......Page 484
GLOSSARY FOR CHAPTER 5......Page 488
ALGEBRAIC GRAPH THEORY......Page 497
6.1.1 The Automorphism Group......Page 498
6.1.2 Graphs with Given Group......Page 499
6.1.3 Groups of Graph Products......Page 501
6.1.4 Transitivity......Page 504
6.1.5 Regularity and Transitivity......Page 506
6.1.6 Graphical Regular Representations......Page 507
6.1.7 Primitivity......Page 508
6.1.8 More Automorphisms of Infinite Graphs......Page 509
References......Page 513
6.2.1 Construction and Recognition......Page 518
6.2.2 Prevalence......Page 520
6.2.3 Isomorphism......Page 521
6.2.4 Subgraphs......Page 524
6.2.5 Factorization......Page 525
References......Page 526
6.3.1 Counting Simple Graphs and Multigraphs......Page 529
6.3.2 Counting Digraphs and Tournaments......Page 533
6.3.3 Counting Generic Trees......Page 536
6.3.4 Counting Trees in Chemistry......Page 540
6.3.5 Counting Trees in Computer Science......Page 541
References......Page 544
6.4.1 Basic Concepts and Definitions......Page 546
6.4.2 The Circuit Subspace in an Undirected Graph......Page 551
6.4.3 The Cutset Subspace in an Undirected Graph......Page 553
6.4.4 Relationship between Circuit and Cutset Subspaces......Page 555
6.4.5 The Circuit and Cutset Spaces in a Directed Graph......Page 558
6.4.6 Two Circ/Cut-Based Tripartitions of a Graph......Page 562
6.4.7 Realization of Circuit and Cutset Spaces......Page 565
References......Page 567
6.5.1 Basic Matrix Properties......Page 570
6.5.2 Walks and the Spectrum......Page 572
6.5.3 Line Graphs, Root Systems, and Eigenvalue Bounds......Page 574
6.5.4 Distance-Regular Graphs......Page 578
6.5.5 Spectral Characterization......Page 581
6.5.6 The Laplacian......Page 583
References......Page 584
6.6.1 Matroids: Basic Definitions and Examples......Page 587
6.6.2 Alternative Axiom Systems......Page 590
6.6.4 Duality......Page 591
6.6.5 Matroid Union and Its Consequences......Page 593
6.6.6 Fundamental Operations......Page 594
6.6.7 2- and 3-Connectedness for Graphs and Matroids......Page 596
6.6.9 Excluded-Minor Characterizations......Page 599
6.6.10 Wheels, Whirls, and the Splitter Theorem......Page 601
6.6.11 Removable Circuits......Page 603
6.6.12 Minimally Connected Graphs and Matroids......Page 606
References......Page 608
GLOSSARY FOR CHAPTER 6......Page 612
TOPOLOGICAL GRAPH THEORY......Page 623
7.1.1 Surfaces......Page 624
7.1.2 Polygonal Complexes......Page 629
7.1.3 Imbeddings......Page 631
7.1.4 Combinatorial Descriptions of Maps......Page 633
References......Page 637
7.2.1 Fundamentals......Page 638
7.2.2 Upper Bounds: Planarity and Upper-Imbeddability......Page 641
7.2.3 Lower Bounds......Page 643
7.2.4 Kuratowski-Type Theorems......Page 647
7.2.5 Algorithmic Issues......Page 649
References......Page 651
7.3.1 Ranges and Distributions of Imbeddings......Page 655
7.3.2 Counting Noncellular Imbeddings......Page 658
7.3.3 Genus Distribution Formulas for Special Classes......Page 660
7.3.4 Other Imbedding Distribution Calculations......Page 663
7.3.5 The Unimodality Problem......Page 666
7.3.6 Average Genus......Page 667
7.3.7 Stratification of Imbeddings......Page 670
References......Page 671
7.4.1 Regular Voltage Graphs......Page 674
7.4.2 Net Voltages, Local Group, and Natural Automorphisms......Page 678
7.4.3 Permutation Voltage Graphs......Page 680
7.4.4 Representing Coverings with Voltage Graphs......Page 681
7.4.5 The Kirchhoff Voltage Law......Page 684
7.4.6 Imbedded Voltage Graphs......Page 685
7.4.7 Topological Current Graphs......Page 687
7.4.8 Lifting Voltage Graph Mappings......Page 689
7.4.9 Applications of Voltage Graphs......Page 690
References......Page 691
7.5.1 Symmetric Imbeddings of Cayley Graphs......Page 697
7.5.2 The Riemann-Hurwitz Equation and HurwitzÌs Theorem......Page 700
7.5.3 Groups of Low Genus......Page 702
7.5.4 Genus for Families of Groups......Page 703
7.5.5 Nonorientable Surfaces......Page 704
References......Page 706
7.6.1 Maps and Polyhedra Maps......Page 709
7.6.2 The Vector and Sequence, and Realizations......Page 712
7.6.3 Map Coloring......Page 715
7.6.4 Minimal Maps......Page 716
7.6.5 Automorphisms and Coverings......Page 718
7.6.6 Combinatorial Schemes......Page 720
7.6.7 Symmetry of Maps......Page 722
7.6.8 Enumeration......Page 726
7.6.9 Paths and Cycles in Maps......Page 727
References......Page 729
7.7.1 Basic Concepts......Page 735
7.7.2 Coloring Densely Imbeddable Graphs......Page 738
7.7.3 Finding Cycles, Walks, and Spanning Trees......Page 740
7.7.4 Re-Imbedding Properties......Page 741
7.7.5 Minors of Imbedded Graphs......Page 743
7.7.6 Minor-Minimal Maps......Page 744
References......Page 746
7.8.1 Basic Concepts......Page 750
7.8.2 Constructing Triangulations......Page 753
7.8.3 Irreducible Triangulations......Page 757
7.8.4 Diagonal Flips......Page 761
7.8.5 Rigidity and Flexibility......Page 766
References......Page 770
7.9.1 Finite Geometries......Page 774
7.9.2 Associated Graphs......Page 778
7.9.3 Surface Models......Page 779
References......Page 781
GLOSSARY FOR CHAPTER 7......Page 783
ANALYTIC GRAPH THEORY......Page 800
Introduction......Page 801
8.1.1 Turán-Type Problems......Page 802
8.1.2 The Number of Complete Graphs......Page 806
8.1.3 Erdos-Stone Theorem and Its Extensions......Page 808
8.1.4 Zarankiewicz Problem and Related Questions......Page 810
8.1.5 Paths and Trees......Page 812
8.1.7 Hamiltonian Cycles......Page 813
8.1.8 Cycle Lengths......Page 814
8.1.9 Szemeredil's Uniformity Lemma......Page 816
8.1.10 Asymptotic Enumeration......Page 817
8.1.11 Graph Minors......Page 819
8.1.12 Ramsey-Turan Problems......Page 820
References......Page 822
8.2.1 Random Graph Models......Page 830
8.2.2 Threshold Functions......Page 833
8.2.3 Small Subgraphs and the Degree Sequence......Page 834
8.2.4 The Phase Transition......Page 837
8.2.5 Many More Properties of Random Graphs......Page 839
8.2.6 Random Regular Graphs......Page 841
8.2.8 Random Graph Processes......Page 843
References......Page 844
8.3.1 RamseyÌs Theorem......Page 850
8.3.2 Fundamental Results......Page 851
8.3.3 Classical Ramsey Numbers......Page 852
8.3.4 Generalized Ramsey Numbers......Page 855
8.3.5 Size Ramsey Numbers......Page 860
8.3.6 Ramsey Minimal Graphs......Page 864
8.3.7 Generalizations and Variations......Page 865
References......Page 867
8.4.1 The First Moment Method......Page 873
8.4.2 Alterations......Page 875
8.4.3 The Lovasz Local Lemma......Page 876
8.4.4 The Rodl Nibble......Page 877
8.4.5 Bounds on Tails of Distributions......Page 878
References......Page 879
GLOSSARY FOR CHAPTER 8......Page 881
GRAPHICAL MEASUREMENT......Page 885
9.1.1 Standard Distance in Graphs......Page 886
9.1.2 Geodetic Parameters......Page 889
9.1.3 Total Distance and Medians of Graphs......Page 893
9.1.4 Steiner Distance in Graphs......Page 894
9.1.5 Distance in Digraphs......Page 896
References......Page 900
9.2.1 Introduction......Page 902
9.2.2 Minimality Conditions......Page 904
9.2.3 Bounds on the Domination Number......Page 907
9.2.4 Nordhaus-Gaddum-Type Results......Page 913
9.2.5 Domination in Planar Graphs......Page 914
9.2.6 VizingÌs Conjecture......Page 915
9.2.7 Domination Critical Graphs......Page 916
9.2.8 Domination Parameters......Page 917
References......Page 918
9.3.1 Intersection Graphs......Page 923
9.3.2 Tolerance......Page 927
References......Page 931
9.4.1 Fundamentals......Page 935
9.4.2 Elementary Results......Page 938
9.4.3 Bounds on Bandwidth......Page 941
9.4.4 On the Bandwidth of Combinations of Graphs......Page 943
9.4.5 Bandwidth and Its Relationship to Other Invariants......Page 945
9.4.6 Related Concepts......Page 949
References......Page 952
GLOSSARY FOR CHAPTER 9......Page 958
GRAPHS IN COMPUTER SCIENCE......Page 965
10.1.1 Breadth-First Search......Page 966
10.1.2 Depth-First Search......Page 969
10.1.3 Topological Order......Page 972
10.1.4 Connectivity Properties......Page 976
10.1.5 DFS as a Proof Technique......Page 982
10.1.6 More Graph Properties......Page 984
10.1.7 Approximation Algorithms......Page 992
References......Page 994
Introduction......Page 998
PART 1: DYNAMIC PROBLEMS ON UNDIRECTED GRAPHS......Page 999
10.2.1 General Techniques for Undirected Graphs......Page 1000
10.2.2 Connectivity......Page 1010
10.2.3 Minimum Spanning Trees......Page 1011
10.2.4 General Techniques for Directed Graphs......Page 1013
10.2.5 Dynamic Transitive Closure......Page 1018
10.2.6 Dynamic Shortest Paths......Page 1021
RESEARCH ISSUES......Page 1024
References......Page 1025
10.3.1 Types of Graphs and Drawings......Page 1028
10.3.2 Combinatorics of Geometric Graphs......Page 1031
10.3.3 Properties of Drawings and Bounds......Page 1035
10.3.4 Complexity of Graph Drawing Problems......Page 1040
10.3.5 Example of a Graph Drawing Algorithm......Page 1041
10.3.6 Techniques for Drawing Graphs......Page 1044
10.3.7 Recent Research Trends......Page 1046
10.3.8 Sources and Related Material......Page 1050
References......Page 1051
Introduction......Page 1059
10.4.1 Algorithms on Trees......Page 1060
10.4.2 Algorithms on Series-Parallel Graphs......Page 1063
10.4.3 Algorithms on Treewidth-Graphs......Page 1066
10.4.4 Algorithms on Cographs......Page 1069
10.4.5 Algorithms on Cliquewidth-k Graphs......Page 1072
10.4.6 Algorithms on k-HB Graphics......Page 1074
References......Page 1077
GLOSSARY FOR CHAPTER 10......Page 1080
NETWORKS and FLOWS......Page 1087
11.1.1 The Basic Maximum Flow Problem......Page 1088
11.1.2 Minimum Cuts and Duality......Page 1089
11.1.3 Max-Flow Min- Cut Theorem......Page 1091
11.1.4 Algorithms for Maximum Flow......Page 1093
11.1.5 Variants and Extensions of Maximum Flow......Page 1096
References......Page 1098
11.2.1 The Basic Model and Definitions......Page 1100
11.2.2 Optimality Conditions......Page 1104
11.2.3 The Dual Problem......Page 1106
11.2.4 Algorithms for Minimum Cost Flow......Page 1107
11.2.5 Extensions to Minimum Cost Flow......Page 1110
References......Page 1113
11.3.1 Matchings......Page 1116
11.3.2 Matchings in Bipartite Graphs......Page 1119
11.3.3 Matchings in Nonbipartite Graphs......Page 1124
References......Page 1128
11.4.1 General Network Design Model......Page 1130
11.4.2 Uncapacitated Network Design......Page 1135
11.4.3 Survivable Network Design (SND)......Page 1139
11.4.4 Capacitated Network Design......Page 1143
References......Page 1149
GLOSSARY FOR CHAPTER 11......Page 1152