o Graph Theory
.....Home Page
o About the Authors
....o Jonathan L. Gross
....o Jay Yellen
o ORDER THE BOOKS
o Graph Theory
.....Resources
....o People
....o Research
....o Writings
....o Conferences
....o Journals
....o The Four-Color
....o    Theorem
....o White Pages
....o White Pages
....o    Registration
o Combinatorial Methods Toolkit NEW!
o Feedback
o Site Correction /
.....Change Request
o Errata in GTAIA 2^ed
o Request an
.....Evaluation Copy
o Graphsong

Last Edited
20 Oct 2007

As seen on
Yahoo, Google, AltaVista, AOL and MSN.
More from AltaVista here

.

© 1999-2007
Aaron D. Gross
Email the Webmaster

Graph Theory Textbooks and Resources

FEATURES

• Provides a unified, up-to-date resource on graph theory
• Explores the algorithmic and optimization approaches of graph theory as well as "pure" graph theory
• Unifies the diversity of graph theory terminology and notation
• Bridges theory and practice with many easy-to-read algorithms

Includes a glossary in each chapter-more than 1000 entries in total

PUBLISHER'S DESCRIPTION
The Handbook of Graph Theory is the most comprehensive single-source guide to graph theory ever published. Best-selling authors Jonathan Gross and Jay Yellen assembled an outstanding team of experts to contribute overviews of more than 50 of the most significant topics in graph theory-including those related to algorithmic and optimization approaches as well as "pure" graph theory. They then carefully edited the compilation to produce a unified, authoritative work ideal for ready reference.

Designed and edited with non-experts in mind, the Handbook of Graph Theory makes information easy to find and easy to understand. The treatment of each topic includes lists of essential definitions and facts accompanied by examples, tables, remarks, and in some areas, conjectures and open problems. Each section contains a glossary of terms relevant to that topic and an extensive bibliography of references that collectively form an extensive guide to the primary research literature.

See also the Table of Contents from the Handbook of Graph Theory.

The ordering of the entries in this index varies slightly from pure alphabetizing, with retrievability considerations occasionally outweighing formal rules. For instance, the entry  “k-coloring” appears with “coloring”. For each term, only the pages on which that term is defined is given. Some entries are accompanied by a hint at the context, with the intent of minimizing effort of retrieval.  Differences of usage of the same word or term in different sections of the Handbook generally reflect the differing preferences of contributors.

• a-approximation algorithm, 979
• a-perfect graph, 433
• c-binding function, 352
• D'-phase, 1095
• DY-transformation of a triangulation, 732
• f-tolerance unit interval graph, 916
• k-absorption, 231
• k-detachment, 231
• k-transformation, 231
• k*-transformation, 231
• m-function (in representativity), 733
• w-perfect graph, 433
• 2-cell imbedding, 618
• 2-opt algorithm, 288
• a.a.s. (= asymptotically almost surely), 412
• [a, b]-factor, 410
• [a, b]-graph, 410
• abstract model for geometry, 766
• acceptance of a string (by automaton), 65
• achromatic coloring, 370
• achromatic number, 370
• acting doubly transitively, 487
• acting freely (group), 670
• acting on a surface (group), 685
• acting regularly (group), 493
• acting semiregularly (group), 493
• acting transitively (group), 486, 670
• active vertex in an s-t network, 1082
• acyclic digraph, 142
• acyclic orientation game, 356
• adding a crosscap to a surface, 614
• adding a vertex to a graph, 14
• adding an edge to a graph, 14
• adding an orientable handle, 614
• additive bandwidth, 939
• adjacency list, 58
• adjacency matrix, 11, 58, 172, 313, 439,
• adjacency matrix, of a digraph, 131
• adjacency matrix, lth-order, 566
• adjacent edges, 3, 629
• adjacent imbeddings (in a stratified graph), 657
• adjacent vertices, 2, 57
• admissible arc in a flow network, 1082, 1096
• agenda in a majority tournament, 175
• agreeing with the circuit orientation, 545
• agreeing with the cut orientation, 545
• algebraic connectivity, 314, 570
• algebraic multiplicity, 557
• all (g, f)-factors, 411
• almost all graphs, property of, 929
• almost every graph, property of, 270
• almost transitive graph, 497
• alphabet, 221
• alteration method of probabilistic proof, 862
• alternating path in a matching problem, 1104
• amalgamation operation, 643
• amendment procedure of voting, 175
• ancestor in a rooted tree, 139, 147, 955
• Andrasfai graphs, 798
• angular resolution in a polyline drawing, 1022
• annulus, 612
• anti-directed path, 163
• antifactor set, 409
• antihole, 433
• antisymmetric digraph, 305
• apex graph, 636
• approximate (or approximation)
• algorithm, 246, 281
• r(n)-approximation, 379
• a-approximation algorithm, 979
• arborescence, 129
• arboricity, 396, 935
• arboricity, k-linear, 414
• arc, 5
• s-arc, 493
• arc-coloring, proper, 137
• arc-coloring lemma, 549
• arc-cut, 129, 216
• arc-disconnecting set, 129
• arc-disjoint paths, 1090
• Archimedean ö-tolerance interval graph, 916
• k-arc-strong digraph, 26
• arc-transitive graph, 491
• area of a drawing, 1022
• c-arrangeable graph, 846
• arrowing a k-tuple (in Ramsey theory), 838
• articulation point (= cutpoint), 967
• aspect ratio of a drawing, 1022
• assignment (= matching), 1106
• asteroidal triple, 441, 911
• asymmetric graph, 485
• asymptotically almost surely, 412, 819
• asymptotically normal, 819
• asymptotically Poisson distribution, 819
• atom, 315
• A-trail (type of eulerian trail), 229
• ATSP (=asymmetric TSP), 279
• attribute, edge 5
• attribute, vertex, 5
• augmenting path, 1090, 1104
• Augmenting Path Theorem, 1105
• automorphism group of a graph, 485, 876
• automorphism of a graph, 485, 876
• automorphism of a map, 705
• automorphism of a simple graph, 505
• availability constraint, 448
• average genus, 654
• axiom of uniqueness (in geometry), 761
• axioms of uniformity (in geometry), 761

• back edge, 59, 956
• backtracking, 460
• backward arc, 1077, 1090
• badness function, 448
• balance condition, 244
• balanced incomplete block design, 761
• balanced orientation, 215
• balanced binary tree, 140
• balanced vertex of a digraph, 215
• bandsize, 936
• bandwidth, 103, 923, 924
• bandwidth of communications, 1118
• bar-amalgamation of two graphs, 643
• 1-barrier, 409
• base graph with regular voltages, 661
• base graph with permutation voltages, 667
• base graphs for recursion, 99, 1046
• base surface for imbedded voltage graph, 673
• base of a matroid, 575
• basic figure, 559
• basic sports timetable (schedule), 462
• basis for recursive construction, 101
• basis of a digraph, 142
• basis of a matroid, 575
• BD (= block design), 762
• beats in a tournament, 156
• bend in a polyline drawing, 1016
• Berge Conjecture (solved), 419
• Berge graph, 433
• Bernoulli random graph, 817
• best improvement k-opt (for TSP), 288
• BEST-Theorem (eulerian tours), 221
• Betti number b(G), 626
• bfs (= breadth-first search), 953
• BIBD (balanced incomplete block design), 761
• biconnected component of a graph, 967
• biconnected graph, 1016
• bicritical graph (re 1-factors), 406
• bicycle, 550
• bicycle-based tripartition, 550
• bidegreed graphs, 84
• bidirectional double tracing, 222
• bifurcated flow, 1120
• bi-hypergraph, 375
• binary constraint satisfaction problem, 924
• binary m-vector, 538
• binary tree, 139, 147, 528, 1016
• binary-search algorithm, 140
• binary-search tree, 140
• binding number, 404
• c-binding function, 352
• binomial random graph, 817
• bipancyclic, 266
• bipartite degree closure, 262
• bipartite index, 202
• bipartite Ramsey number, 853
• bipartite graph, 24, 438
• bipartite graph characterization, 25
• bipolar digraph, 1016
• bits per second (bps), 1118
• block design, 762
• block in a graph, 196
• block of permuted objects, 495
• bond matroid, 578
• bonds, 579
• Bondy-Chvatal Theorem, 801
• Bondy-Erdos Conjecture (Ramsey numbers), 843
• book (2-complex), 617
• r-book (type of graph), 792
• boundary vertices of a subgraph, 991
• boundary of a surface, 611
• boundary-separating closed curve, 646
• boundary-walk specification, 616
• bounded automorphism, 499
• bounded min-tolerance interval graph, 915
• bouquet, 4, 20, 648, 664
• branch points if a branched covering, 669
• branch set of a branched covering, 669
• branch-decomposition of a graph, 105
• branched covering, 669
• branchwidth of a graph, 106
• breadth-first search, 953
• breadth-first algorithm, 61, 955
• breadth-first tree, 60, 61, 955
• break in a schedule, 136, 464
• breakpoint in a flow network, 1097
• bridge components (BCs), 967
• bridge tree, 967
• bridge, 195, 967, 970, 977
• bridges algorithm, 968
• Brooks’s Theorem (for chromatic number), 345

• cactus, 636
• cage, 309, 493, 765
• canonical factors and form of finite abelian group, 691
• canonical numbering algorithm, 69
• canonical ordering, 69
• canonical factor in scheduling, 468
• capacitated concentrator location, 1132
• capacitated vehicle-routing problem (CVRP), 292
• capacitated communication facility, 1118
• capacity in a flow network, 1075, 1084
• capacity of an s-t cut, 1077
• capacity of flow-augmenting path, 1079
• capacity-scaling algorithm (for minimum-cost flow), 1095
• cartesian product, 14, 269, 489, 569, 900, 939
• Carving Lower Bound, 980
• Catalan numbers, 530
• Catalan triangulation, 738
• categorical product, 489
• Cayley digraph, 317
• Cayley graph, 22, 317, 505, 662, 684
• Cayley map for a group, 685, 710
• Cayley’s formula (for labeled trees), 524
• CCL (capacitated concentrator location), 1132
• 2-cell imbedding, see cellular imbedding
• 0-cell, 1-cell, 2-cell, 616
• cell-distribution vector (f-vector), 699
• cellular imbedding, 618, 625, 698, 722
• center of a graph, 16, 875
• center of a strong digraph, 885
• k-center, 883
• central vertex, 16, 875
• k-central vertex, 883
• centroid of a triangle, 763
• certificate, 69, 994
• characteristic polynomial of a graph, 557
• characteristic vector of a subset of vertices, 392
• child in a rooted tree, 139, 147, 528
• child-node in a backtracking tree, 71
• Chinese Postman Problem, 225, 237
• Chinese Postman algorithms, 240, 242, 245, 247, 249
• chiral map, 710
• choice index for hypergraphs, 374
• choice number for hypergraphs, 374
• choice number (= list chromatic number), 343
• (f, g)-choosable graph, 365
• k-choosable graph, 343
• chordal graph, 101, 416, 440, 912
• chords, 536
• Christofides heuristic algorithm (for TSP), 287
• chromatic index of a hypergraph, 374
• chromatic index, 351
• chromatic number, 7, 342, 432, 934, 1057
• chromatic number of hypergraph, 374
• chromatic polynomial, 369
• chromatic sum (= color cost), 372
• chromatic surplus, 843
• b-chromatic number, 371
• k-chromatic graph, 342
• Chvatal’s Theorem (for perfect graphs), 437
• Chvatal-Erdos Theorem, 801
• CI-graph, 509
• CI-group, 509
• circ (= closed trail), 538
• circle-packing theorem, 701
• circuit, 264, 536
• circuit matrix, 545
• circuit orientation, 545
• circuit space, 548
• circuit subspace, 539
• circuit vector of a graph, 542
• circuit vector of a digraph, 545
• circuits in a matroid, 574
• circulant graph, 22, 317, 505
• circular coloring, 371
• circular imbedding, 722
• circulation (in a transshipment network), 1088
• circumcenter of a triangle, 763
• circumference, 273, 800
• Clarke-Wright savings algorithm (for
• class edge-reconstruction number, 85
• class reconstruction number, 85
• Class 1 and Class 2 (for edge-chromatic number), 354
• claw, 404
• claw-free closure, 273
• claw-free graph, 84, 404
• clean triangulation, 738
• clique, 389, 431, 1056
• s-clique, 789
• clique cover of a graph, 431
• clique cover, f-T-edge, 918
• clique cover, p-edge, 914
• clique hypergraph, 376
• clique incidence matrix, 436
• clique number, 301, 389, 431, 789
• clique partition number, 416
• cliquewidth-k graph, 108, 1059
• closed disk, 611
• closed-end ladder, 647
• closed face, 722
• closed interval in a graph, 877
• closed neighborhood, 394, 890
• closed set in a matroid, 577
• closed surface, 612
• closed trail, 536
• closed under duality (class of matroids), 579
• closed under minors (class of graphs), 634, 730
• closed walk, 9
• closure of a graph, k-degree, 262
• closure of a set of edges in a matroid, 577
• closure (hamiltonian), 800
• cluster in a dynamic graph, 987, 991
• clusters in TSP, 289
• coalescence (= amalgamation), 569
• cobases in a matroid, 578
• cobblestone path graph, 647
• cocircuits in a matroid, 578
• cocktail-party graph, 559
• cograph, see complement reducible graph
• cographic matroid, 578
• coindependent sets in a matroid, 578
• coloops in a matroid, 578
• color automorphism problem, 73
• color bound for Precoloring Extension, 373
• color class of vertices, 70, 342
• color class of edges, 463
• color cost, 372
• (r, s)-colorable graph, 805
• k-colorable graph, 7, 342
• L-colorable graph (list), 343
• colorable hypergraph, 375
• color-class adjacency matrix, 70
• color-class size vector, 70
• coloring number of a hereditary property, 805
• coloring number (Erdos-Hajnal), 345
• coloring of a graph, 70
• coloring, partial, 373
• coloring, total, 352
• l-coloring, 371
• b-coloring, 370
• H-coloring of, 372
• k-coloring of a graph, 342
• T-coloring, 371
• color-preserving graph mapping, 70
• combinatorial geometry, 577
• combinatorially equivalent triangulations, 738
• commodity, 1084, 1118
• communication facility, 1118
• compact schedule, 136, 465
• comparability digraph, 150
• comparability graph, 440
• competition graph, 913
• competition number, 913
• competition graph,f-tolerance, 918
• p-competition graph, 914
• complement (= edge-complement), 432, 929
• complement of a subgraph in a graph, 534
• complement-reducible graphs, 107
• complementarity property for a schedule, 466
• complementarity in min-cost network flow, 1091
• complementary numbering, 927
• complementary profiles in scheduling, 464
• Complementary Slackness Theorem, 1091
• complete k-ary tree of depth d, 926
• complete k-partite graph, 25, 791, 925
• complete m-ary tree, 147
• complete axiom system, 766
• complete bipartite graph, 25
• complete digraph, 20, 128
• complete graph, 20
• complete isomorphism invariant, 657
• complete matching, 1106
• complete multipartite graph, 25
• complete set of forbidden minors, 634
• complete r-uniform hypergraph, 375
• completeness constraint, 448
• completion of a transshipment network, 1094
• complex graph (compare dense), 824
• component factor (type of factor), 403
• component of a graph, 13, 195, 536
• composition G[H], 743, 931
• composition in recursive construction, 107, 1046
• concatenation of strings, 65
• concrete model for geometry, 766
• concurrent flow problem, 1084
• condensation tournament, 161
• condensation of a digraph, 128, 964
• conditional connectivity, 320
• conditional domination number, 904
• conditional edge-connectivity, 320
• Condorcet paradox, 174
• Condorcet winner, 174
• 3-configuration, 762
• (r, k)-configuration, 762
• conflict graph, 453
• conflict in scheduling, 452, 457
• congestion at an edge, 676
• congestion of a graph mapping, 676
• congruent imbeddings, 650, 753
• connected digraph, 127
• connected graph, 10, 194, 536
• connected Ramsey number, 853
• connected sum of surfaces, 614
• 2-connected matroid, 583
• 3-connected matroid, 585
• k-connected graph, 26, 196, 263, 789
• connection set for a Cayley graph, 22, 505
• connectivity requirement (in a communications network), 1127
• connectivity, t-distance, 321
• connectivity, 25, 129, 195, 197, 263
• consecutive 1’s property in a matrix, 439
• consistent set of arcs in a tournament, 167
• consistent axiom system, 766
• consistently oriented 2-complex, 616
• constraint graph, 924
• construction heuristic, 397
• continuous model for min-cost flow, 1097
• contractible curve on a surface, 614, 723
• contractible edge in triangulation, 744
• k-contractible edge, 204
• k-contractible subgraph, 205
• contraction of edge, 111, 204, 703, 928
• contraction of matroid, 581
• contraction of triangulation, 744
• convex drawing, 1017
• convex hull of a vertex set, 878
• convex graph property, 818
• convex set of vertices, 878
• convolution of two sequences, 643
• k-core of a graph, 824
• corona of two graphs, 894, 931
• correctness property of drawing checker, 1034
• coset of a subgroup, 318
• cospanning tree (= co-tree), 536, 629
• cost chromatic number, 372
• cost flow network, 137
• cost of a coloring, 372
• cost set for coloring, 372
• co-tree, 536, 629
• course timetable, 452
• cover graph of a poset, 150
• cover for reconstruction, 88
• covering a poset element, 150
• covering projection, 668
• covering projection, regular, 670
• covering space, 668
• covering space, regular, 670
• covering transformation, 670
• covering walk (= postman tour), 138, 222
• covering with folds, 743
• Coxeter complex, 706
• Coxeter group, 705
• Coxeter regular skew polyhedra, 711
• critical imperfect graph, 441
• critically k-chromatic, 26, 346
• critically k-connected, 26
• critically k-edge-connected, 26
• critically n-connected, 207
• k-critically n-connected, 207
• cross edges, 59, 956, 957
• crosscap distribution polynomial, 643
• crosscap distribution sequence, 643
• crossing number of a drawing, 1022
• crosscap number of a graph, 618, 626, 643
• crosscap number of a group, 692
• crosscap number of an imbedding, 625
• crosscap number of a surface, 614, 692
• crossing (of edges), 1016
• d-cube graph, 22
• current assignment, regular, 674
• current graph, 674
• current group, 674
• cut (an edge set), 537, 1127
• cut (a vertex set), 129
• cut condition for incidence partition, 227
• cut-edge, 14, 195
• cut matrix, 546
• cut orientation, 545
• cut vector, 542, 545
• cut-vertex, 14, 195
• s-t cut, 1077
• cutpoint, 14, 967
• cutset, 129, 537
• cutset space, 548
• cutset subspace, 540
• cutwidth, 938
• CVRP tour (for vehicle routing), 291
• cycle (= closed path), 9
• cycle, in a digraph, 163
• cycle-canceling algorithm (for minimum-cost flow), 1092
• cycle cover, 224
• cycle decomposition, 215
• cycle-decomposition transition system, 227
• cycle double cover, 224
• cycle double-cover conjecture, 224, 699
• cycle extendable, 266
• cycle flow, 1099
• cycle graph, 20
• cycle packing, 224
• cycle rank, 24, 626, 654
• cycle-shift, of a bitstring, 253
• cycle-shift 2-factor, 254
• cycle-shift arc, 254
• cyclic bandwidth, 936
• cyclically k-edge-connected, 354
• cylinder, 612

• DAG (directed acyclic graph), 142, 960
• daisy (= subdivided bouquet), 895
• dead end of a dfs path, 968
• deBruijn 2-factor, 254
• deBruijn arc, 254
• deBruijn graph of order k, 254
• deBruijn graph, 221
• deBruijn sequence of order k, 253
• deBruijn sequence, 221
• deBruijn shift, 253
• deBruijn’s Theorem, 255
• deBruijn graph of order k, S-relative, 259
• decision tree, 175
• deck for reconstruction, 79
• decomposable into complete subgraphs, 902
• H-decomposition Problem, 416
• decomposition in timetabling, 461
• decomposition tree for recursively constructible graph class, 99, 1046
• decreasing property of graphs, 818
• decremental dynamic graph problem, 986
• deficiencyxG) of a graph, 629
• deficiency of a branch point, 687
• d-degenerate graph, 345
• degree factor, 403
• Degree Lower Bound, 980
• degree of a graph, 8, 57
• degree of a permutation group, 487
• degree sequence, 8, 932
• degree vector of a graph coloring, 70
• Delaunay drawable, 1018
• Delaunay triangulation, 1018
• deleting an edge from an imbedding, 627
• deleting an edge, operation, 14
• deleting a vertex, operation 14
• deletion operation for matroids, 581
• demand in a flow network, 1084, 1118
• dense graph, 57
• dense imbedding, 723
• dependent set in a matroid, 575
• depth of vertex in rooted tree, 139, 147
• depth-first forest, 59, 956, 957
• depth-first search, 956
• depth-first search algorithm, 60, 958
• depth-first tree, 59, 956
• derived digraph (permutation), 667
• derived digraph (regular), 661
• derived graph of voltage graph, 662, 663
• derived imbedding of a current graph, 674
• derived imbedding of a voltage graph, 673
• derived surface of voltage graph, 673
• Desargues’s Theorem, 763
• descendant in a rooted tree, 139, 147, 955
• descendant, proper, 139, 955
• destination node, 1118
• detachment operation, 218, 219
• dfs (depth-first search), 956
• dfs tree, 956
• diagonal flip, 748
• P-diagonal flip, 751
• diagram-tracing puzzles, 30
• diameter, 10, 301, 874, 934, 954
• diameter of a strong digraph, 884
• k-diameter, 882
• digon (= 2-sided polygon), 673
• digraph representation of a relation, 134
• digraph, 6, 57
• Dijkstra’s algorithm, 134
• dipole, 4, 20, 664
• Dirac’s Theorem, 800
• direct product (or conjunction), 269
• direct product (= cartesian product), 434
• direct sum, 581
• Directed Chinese Postman Problem, 138
• directed circuit, 549
• directed cutset, 549
• directed distance, to or from, 10
• directed distance, 883
• directed edge, 5
• directed graph, 6, 57
• directed tree, 129, 145
• directed version of CPP (DCPP), 237
• directed walk, 9, 127
• disconnecting edge-set, 195
• disconnecting vertex-set, 129, 195
• disconnecting set, 129
• (u|v)-disconnecting set, 198
• discovered vertex in graph search, 958
• discovery order of vertices, 959
• discrete model, 1097
• disk, 611
• distance between two subgraphs, 881
• distance between two vertex subsets, 302
• distance between two vertices, 10, 873, 954
• distance function, 1082
• distance graph, 357
• distance matrix, 280
• distance-regular, 319, 565
• 1+1 diverse path protection, 1133
• diversification in a network, 1134
• divisible into t isomorphic subgraphs, 416
• division tree, 176
• divisor under a graph product operation, 489
• DNA sequence, 259
• dominance drawing, 1017
• dominating circuit, 265
• dominating set, 889, 890, 1057
• dominating set, minimum, 889
• domination chain, 893
• domination critical, 903
• domination graph of a tournament, 171
• domination in a flow graph, 977
• domination in a tournament, 156, 171
• domination number in a tournament, 171
• domination number, 889, 890
• dominator tree, 977
• double jump, 824
• double tracing, 222
• doubly-periodic graph, 379
• doubly-regular tournament, 158
• drawable as a minimum spanning tree, 1020
• drawing checker, 1034
• hv-drawing (of a graph), 1017
• dual M* of a matroid, 578
• dual feasible, 1093
• dual map for any graph imbedding, 697
• dual prices, 1091
• dual linear programming problem, 1093
• dual of a planar graph (= Whitney dual), 554
• dual of a voltage graph, 674
• Dyck map, 711
• dynamic graph, 985
• dynamic programming algorithm, 152

• ear, 627
• ear, attaching a closed, 654
• ear, attaching an open, 654
• ear decomposition, 627, 973
• ear decomposition, 3-connected, 628
• ears, serially attached, 655
• Eberhard’s Theorem, 700
• eccentricity, 10, 873, 884
• 2-ECSS algorithm, 979
• k-eccentricity, 882
• k-ECSS, 979
• edge of a graph, 2
• edge, proper, 3
• edge of a map, 696
• edge-automorphism, 487
• edge-bandwidth, 937
• edge choice number, 352
• Edmonds’s Branching Theorem, 977
• Edmonds’s Theorem (for general
• edge-chromatic number, 7, 449, 934
• edge clique cover, 910
• c-edge-colorable, 7
• edge-coloring, 7
• edge-coloring, proper, 351, 374, 449
• k-edge-coloring, 838
• edge-complement, 14, 432
• edge-complement of a subgraph, 534
• k-edge-connected graph, 26, 196, 223, 979
• edge-connectivity, 25, 129, 195, 197, 223, 304
• t-distance edge-connectivity, 321
• edge-contraction, 111, 703
• edge-cut, 129, 195, 216
• edge-deck for reconstruction, 79
• edge-deleted subgraph for one edge, 79
• edge-deletion subgraph for subset of
• edges, 195
• edge-density model, 270
• edge design, 1119
• edge difference polynomial, 344
• edge-disconnecting set, 129
• edge-extraction, 111
• edge-face equality, 631
• edge-face inequality, 631
• edge fiber for a voltage graph, 663
• edge-group, 487
• edge-isomorphism, 487
• edge-multiplicity, 3
• edge-numbering, 936
• edge-recognizable class of graphs, 83
• edge-reconstructible class of graphs, 80
• edge-reconstruction conjecture, 80
• edge-reconstruction number, 85
• edge-reconstruction of a graph, 80
• k-edge-reconstruction, 91
• (u|v)-edge-set, 321
• edgesum, 936
• edge-symmetric, 316
• edge-transitive, 12, 316, 416, 491
• edge-width of a graph imbedding, 697, 723
• Edmonds’s Branching Theorem, 977
• Edmonds’s Theorem (for general matching), 1112
• eigenvalues of a graph, 557
• eigenvalues-diameter (lower) bound, 560
• elementary figure, 559
• elementary graph, 89
• empty graph, 20, 534
• end-equivalent rays, 496
• endomorphism, 496
• endoskeleton of a triangulation, 1019
• endpoints of an edge, 2
• endvertex-deck for reconstruction, 85
• equivalent triangulations under diagonal flips, 748
• equivalent triangulations under homeomorphism, 753
• equivalent panel structures, 755
• YDY-equivalent triangulations, 732
• Erdos conjecture (about tournaments), 170
• Erdos–Faber–Lovasz conjecture, 350
• Erdos-Renyi graph, 797
• Erdos-Renyi random graph, 818
• Erdos-Sos conjecture, 799, 843
• Erdos-Stone Theorem, 795
• ES (algorithm for postman problem), 247
• essential cycle in a graph imbedding, 615, 747
• a-essential ray, 500
• ET tree in a dynamic graph, 990
• Euclidean crystallographic group, 689
• Euclidean space group, 689
• Euclidean TSP, 280
• Euler characteristic, 614
• Euler theorem on degree sum, 8
• Euler genus of a surface, 692, 723
• Euler genus of a group, 692
• Euler Polyhedral Equation, 619, 626
• Euler tour, 990
• Euler’s formula, 698
• Euler’s polyhedron formula, 35
• eulerian spanning subgraph, 355
• eulerian tour, 137, 215, 238
• eulerian-tour-type algorithms, 233, 240, 242, 245, 247, 249
• eulerian trail, 9
• eulerian triangulation, 726
• eulerian graph, 26, 215, 238
• eulerian-tour transition system, 227
• even component, 629
• even vertex on an alternating path, 1111
• even graph, digraph, or mixed graph, 215,
• even-symmetric, 247
• event (for random graphs), 818
• exact algorithm, 281
• excess of a graph, 824
• excess flow, 1082, 1095
• excluded minor, 586
• expanded blossom, 1111
• exponential growth, 491
• extended flow network, 1087
• external degree, 987
• external face, 1017
• extremal function, 790
• extremal graphs, 790

• face of a 2-complex, 616
• face of a drawing of a graph, 1017
• face of a graph imbedding, 618, 625
• faces of a GEM, 708
• faces of a map, 696
• faces of a permutation scheme, 708
• face-size sequence (p-sequence) of a map, 699
• face-tracing algorithm, 621
• face-width of a map, 697
• face-width of an imbedding, 723
• facility capacity, 1118
• facility levels, 1118
• facility, 1118
• factor of a graph, 403,
• factor in timetabling, 463
• factor, almost regular, 410
• factor, semiregular, 410
• 1-factor, 404, 1103
• [a, b] factor, 410
• (g, f)-factor, 411
• f-factor, 409
• F-factor, 413
• G-factor, 416
• G-factor recognition problem, 416
• H-factor, 793
• k-factor, 21, 265, 403, 408
• r-factor in timetabling, 463
• factorization, 403, 512
• d-factorization in timetabling, 463
• Fano matroid, 587
• Fano plane, 764
• farthest vertex insertion (FVI), 286
• feasible flow, 1075
• feasible flow, standard, 1088
• feasible multicommodity flow, 1084
• feasible (timetabling), 448, 452, 469
• feedback set of arcs, 166
• fiber-preserving homeomorphism, 670
• algorithm, 1081
• fiber in a graph covering, 663, 669
• final vertex of a walk, 9
• finish-time order of a search, 959
• finite affine plane, 762
• finite automaton, 64
• finite geometry, 761
• finite projective plane, 762
• first-moment method, 860
• Five Color Theorem, 367
• fixed cost in communication network, 1118
• fixed parameter tractable problem, 1036
• fixed-size model, 270
• flag, 706, 709
• flat in a matroid, 577
• Fleury’s algorithm (eulerian tours), 218
• 2-flip (= Whitney flip), 728
• flow, 225, 1119
• s-t flow, 1088
• flow across cut, 1078
• flow-augmenting path, 1079
• Flow Augmentation Theorem, 1079
• flow decomposition, 1099
• flow graph, program, 974
• flow over time, 1098
• flow with gains, 1100
• flow, standard 1088
• Floyd-Warshall (all-paths) algorithm, 63
• forbidden graphs, 790
• forbidden minors, 112
• Ford-Fulkerson (maximum flow) algorithm, 1081
• forest, 16
• forest, k-linear, 414
• forward arc (for spanning tree), 1077, 1090
• forward edge (for spanning tree), 59, 956
• four-color problem, 39
• Four Color Theorem, 367, 702
• FPT class, 1036
• fractional chromatic number, 365
• fractional vertex-coloring, 365
• free edge for a matching, 1103
• free vertex for a matching, 1103
• free action of an automorphism group,
• H-free (of a subgroup H), 789
• frontier arc, 129
• frontier edge, 16
• frozen triangulation, 748
• Frucht’s Theorem, 488
• full triangle group, 688
• fully cycle extendable., 266
• fully dynamic connectivity, 986
• fully dynamic minimum spanning tree,
• fully dynamic graph problem, 986
• functional graph, 149
• fundamental circuit matrix, 546
• fundamental circuit, 539
• fundamental cutset, 541, 546
• fundamental polygon, 617

• Gabriel graph, 1020
• gain factor, 1099
• gain network, 1099
• gainy arc, 1100
• gas-water-electricity problem, 37
• GEM (graph encoded map), 708
• general graph, 4
• generalized p-cycle, 306
• Generalized Asymmetric Traveling Salesman Problem (GATSP), 289
• generalized dicyclic group, 494
• generalized line graph, 562
• generalized rotation, 621
• Generalized Symmetric Traveling Salesman Problem (GSTSP), 289
• genus of a finite geometry, 766
• genus of a graph, 26, 618, 625
• genus of a group, 684
• genus of a surface, 614
• genus distribution polynomial, 643
• genus distribution sequence, 642
• genus imbedding, 618
• genus range of a graph, 642
• geodesic (in an infinite graph), 500
• geodesic (in a finite graph), 873
• geodetic iteration number, 878
• geodetic number, 877
• geodetic set, 877
• geodetic (in an infinite graph), 500
• s-geodetic digraph, 322
• geometric multiplicity, 558
• geometric realization, 699
• geometry, 761
• geometry of Desargues, 763
• geometry of Pappus, 763
• geometry, n-point, 762
• girth, 300, 631, 800, 935
• Golomb postulates of randomness, 258
• graph G(P) of a communication channel, 434
• graph automorphism, 12
• graph encoded map, 708
• graph isomorphism problem, 68
• graph of the map, 696
• graph polynomial, 344
• graph process, 270
• graph product, 488
• graph property, 804
• graph union, 15
• graph, 2, 620
• [a, b]-graph, 410
• m/3 -graph, 898
• (n, k)-graph, 207
• graphical regular representation, 494
• graphical sequence, 404
• greedy algorithm (for matroids), 578
• greedy heuristic algorithm (for TSP), 284
• grid drawing, 1016
• Grotzsch graph, 798
• Grotzsch’s Theorem, 367
• ground set for a matroid, 574
• (p, q, r)-group, 688
• (p, q, r)^o-group, 688
• growth, 491
• GRR, 494
• Grundy coloring, 370
• Grundy number, 370
• guest in a graph mapping, 676

• H-decomposition Problem, 416
• Hadwiger’s conjecture (for chromatic number), 351
• Hajos’s conjecture (for chromatic number), 351
• half degree of a vertex of a digraph, 206
• half disk, 611
• half-edges, 620
• half-transitive graph, 491
• Halin graph, 102
• Hall’s Theorem, 407, 1107
• Hamilton decomposition, 512
• hamilton-connected graph, 261, 323, 511
• hamilton-laceable graph, 511
• hamiltonian cycle, 160, 261
• hamiltonian decomposition, 269
• hamiltonian graph, 26, 31, 261, 800
• hamiltonian graph, k-ordered, 266
• hamiltonian path, 160
• Hamming distance, 391
• Hamming graph, 391, 565
• harmonious coloring, 371
• Hasse diagram, 150
• k-HB (homogeneous balanced) graphs, 110, 1061
• head of a directed edge, 5, 127
• Heawood formula, 702
• Heawood graph, 309, 494
• Heawood Map Coloring Theorem, 702
• Heawood number, 368, 631
• height of a rooted tree, 139, 147
• hereditary graph property for minors, 730
• hereditary for induced subgraphs, 805
• hierarchical drawing, 1017
• hierarchical generating set for a group, 318
• Hierholzer’s algorithm (eulerian tours), 217
• hitting time (for random graphs), 830
• Ho.man polynomial, 561
• hole in a graph, 433
• homeomorphic graphs, 636
• homeomorphically reduced tree, 524
• k-HB (homogeneous balanced) graphs, 110, 1061
• homomorphic graphs, 798
• homomorphism of graphs, 371
• Hopcroft and Tarjan planarity algorithm, 972
• host of a graph mapping, 676
• hull number, 878
• hull set, 878
• Hurwitz formula, 707
• Hurwitz group, 691
• hv-drawing (of a graph), 1017
• hypercube characterization theorem, 23
• hypercube graph, 22, 925
• hyperedges, 68
• hypergraph, 374, 375, 853
• hypergraph imbedding, 708
• hypermap, 708
• hyperplane, 577
• hypohamiltonian graph, 408
• hypotraceable graph, 408

• icosian game (hamiltonian graphs), 261
• illegitimate deck problem, 93
• illegitimate deck, 93
• image of an imbedding, 625
• imbeddable on a surface, 313
• imbedded (di)graph, 1017
• imbedded voltage graph, 673
• imbedding of a graph, 618, 625
• immediate dominator, 977
• immersion of a graph, 618
• imprimitive group action, 495
• improvement LS (local search), 397
• in-arcs of a cut, 216
• in-branching in a digraph, 169
• incenter of a triangle, 763
• incidence matrix of directed graph, 546
• incidence matrix, 58
• incidence set of a vertex, 216, 537, 541
• incidence vector, 542
• incidence-partition system, 227
• incident faces of a map, 708
• incident, 2, 708
• increasable flow, 1079
• increasing property, 818
• incremental, 986
• in-degree of a vertex in a digraph, 8, 157
• independence number, 262, 389, 482, 465, 789, 892, 935
• independent domination number, 892
• independent set, 199, 262, 389, 432, 453, 465, 892, 1046
• independent set in a matroid, 575
• independent axiom system, 766
• independent-set cover, 432
• independent-set incidence matrix, 436
• induced imbedding, 621
• induced Ramsey number, 853
• induced subgraph on an edge set or vertex set, 534
• induced subgraph, 13
• induced digraph from voter preferences, 174
• in-eccentricity, 322
• infinite connectivity, 499
• initial vertex of a walk, 9
• in-score, 157
• inserting a new edge into an imbedding, 627
• in-set, 157
• integer flow, 225
• integer program (IP), 1118
• integrality gap, 1122
• interconnection network, 748, 924
• interior of a contractible cycle, 723
• interior vertex, 315
• interlacing segments on a cycle, 971
• intermediate growth of a function, 491
• internal vertex of a tree, 147
• internal vertex of a path, 9, 197, 977
• internally-disjoint paths, 197
• intersection graph for subsets, 439, 910
• p-intersection graph, 914
• intersection graph, f-tolerance, 914
• intersection number, 910
• p-intersection number, 914
• interval graph, 439, 911
• interval graph, f-tolerance proper, 916
• interval model, 439
• in-tree (type of directed rooted tree), 146, 169, 220, 242
• invariant, see isomorphism invariant
• irreducible schedule, 465
• irreducible tournament, 157
• irreducible triangulation, 745
• irredundance number, 892
• irredundant set of vertices, 892
• ISO (= graph isomorphism problem), 68
• isolated vertex, 8
• Isomorphic Factorization Problem, 416
• isomorphic factorization, 512
• isomorphic graphs, 11, 68
• isomorphic maps, 697
• isomorphic triangulations, 738
• isomorphism of general graphs, 11
• isomorphism of simple graphs, 10
• isomorphism-complete problem, 74
• isomorphism invariant, 11
• isomorphism of labeled graphs, 68
• isomorphism of matroids, 575
• isomorphism of permutation groups, 487
• isomorphism, 68
• isotopic, 738

• jackknife operation, 100, 124, 1050
• jellyfish pseudosurface, 612
• Johnson graph, 565
• join operation on two graphs, 14
• joining two vertices, 2
• 2-join in a graph, 442
• kappa transformations (for eulerian tours), 231
• Kepler-Poinsot regular star polyhedra, 710
• kernel for a surface, 733
• key (type of graph), 895
• k-flow (bounded integer flow), 225
• king in a tournament, 168
• Kirchhoff matrix of a digraph, 220
• Kirchoff current law (KCL), 675
• Kirchoff voltage law (KVL), 672, 742
• Kleene’s algorithm, 66
• Kleene closure of a set of strings, 65
• Klein bottle, 613
• Klein map, 711
• knight’s tour problem, 31
• Konig’s Edge-Coloring Theorem, 417
• Konig’s Theorem (edge-chromatic number), 450
• Konig’s Theorem (vertex-cover and matching), 407, 1107
• Konigsberg Bridges Problem, 29, 214
• Kotzig’s Theorem, 969
• Kuratowski graphs, 37
• Kuratowski’s Theorem, 554, 628

• labeled digraph, 520
• labeled graph, 68, 516
• labeled tree, 523
• L(2, 1)-labeling, 371
• ladder graph, 647
• language, 65
• Laplacian eigenvalues, 314
• Laplacian matrix, 314, 570
• large edge-width imbedding, 697, 728
• lattice graph, 563
• layered (di)graph, 1016
• layered drawing, 1017
• leaf generated representation, 917
• leaf, 147
• k-leaf-connected graph, 323
• left (right) subtree of a binary tree, 139
• left child in a binary tree, 139, 147
• left-right tree, 528
• length function on a graph, 954
• length of a directed walk, 127
• length of a walk, 9
• less than, in a poset, 150
• level in a tree, 139, 147
• Levi graph, 765
• LEW-imbedding, 728
• lexicographic product, 269, 489
• lift of a walk in a voltage graph, 672
• lifted boundary walks, 673
• line digraph, 307
• line graph, 26, 264, 302, 352, 438, 561, 937
• line graph characterization, 27
• linear extension ordering, 151
• linear program (LP), 1118
• linear programming relaxation, 1122
• lines of a geometry, 761
• link in a triangulation, 738
• k-linked graph, 202
• list assignment, 343
• list chromatic index, 352
• list chromatic number, 343
• list-L colorable, 343
• list coloring of a hypergraph, 374
• list edge chromatic number, 352
• load of a mapping at a vertex, 676
• load of a mapping (global), 676
• local access network, 1122
• local completion of a graph, 273
• local group of a voltage graph, 665
• local improvement, 397
• local search (LS) heuristic, 397
• logarithmic density of a graph property, network, 1127
• long paths property, 1003
• loop in a matroid, 577
• loopless graph, 4
• lossy arc, 1100
• Lovasz Local Lemma, 863
• Lovasz-Woodall conjecture, 201
• Lovasz parameter .(G), 437
• low connectivity survivable [LCS] network, 1127
• lower chromatic number of a hypergraph, 375
• Lyndon word (class of binary strings), 257

• Mobius band (or strip), 613
• Mobius ladder, 506, 798
• majority digraph, 174
• manifold, 611
• map (on a surface), 696
• map covering, 705
• map minor, 714
• map of a rotation scheme, 707
• map of type {p, q}, 699
• Marczewski’s Theorem, 911
• Markov digraph, 133
• Markov chain, 132
• Marriage Theorem, 407
• matched edges or vertices, 1103
• matching lower bound, 980
• matching, 202, 239, 389, 1057, 1103
• matching, complete, 1106
• matching number, 407
• mate vertex in a matching, 1103
• Matrix Tree Theorem, 221, 548
• matroid, 574
• Max-Flow Min-Cut Theorem, 1079
• maximal run in a binary sequence, 258
• maximally connected digraph, 198
• maximally connected graph, 196
• maximally distant trees, 550
• maximally edge-connected digraph, 198
• maximally edge-connected graph, 196
• maximum clique, 460
• maximum-clique (in a cograph) algorithm, 1057
• maximum-clique problem, 389
• maximum crosscap imbedding, 618
• maximum crosscap number, 618, 626, 643
• maximum density of a graph, 821
• maximum s-t flow over time, 1098
• maximum-flow characterization, 1079
• maximum-flow problem, 137, 1076, 1089
• maximum flow with gains, 1100
• maximum genus imbedding, 618
• maximum genus, 618, 626, 642
• maximum-independent-set problem, 389
• maximum-independent-set (in a cliquewidth-k graph) algorithm, 1060
• maximum-independent-set (in a cograph) algorithm, 1057
• maximum-independent-set (in a k-HB graph) algorithm, 1062
• maximum-independent-set (in a seriesparallel graph) algorithm, 1051
• maximum-independent-set (in a tree) algorithm, 1048
• maximum-independent-set (in a treewidth-k graph) algorithm, 1053
• maximum-weight-independent-set problem, 390
• maximum-matching (in a bipartite graph) algorithm, 1109
• maximum-matching (in a cograph) algorithm, 1058
• maximum-matching (general) algorithm, 1112
• maximum-multicommodity-flow problem, 1084
• maximum nonorientable genus, 643
• maximum number of bends of a polyline drawing, 1022
• maximum-size matching, 1103
• maximum-tolerance interval graphs, 915
• maximum-weight bipartite matching, 1090
• maximum-weight-clique problem, 390
• maximum-weight cycle-packing problem, 224
• maximum-weight-independent-set problem, 390
• maximum-weight-independent-set (in a tree) algorithm, 1049
• maximum-weight matching, 1103
• maximum-weight matching (in a bipartite graph) algorithm, 1110
• medial graph, 723
• median subgraph M(G), 880
• median vertex, 880
• meeting (in timetabling), 447
• memetic algorithms (in timetabling), 461
• Menger graph, 765
• Menger’s Theorem, 199
• merger of cycles, 293
• merger of faces, 627
• merger of vertices, 928
• metric ray, 500
• metric type, of a ray, 500
• minimal clean triangulation, 747
• minimal dominating set, 891
• minimal forbidden minor, 634
• minimal generating Cayley set, 512
• minimal generating set for a group, 317
• 2/5-minimal graph, 895
• minimal polynomial, 560
• minimal triangulation, 704
• minimally k-connected graph, 206, 593
• minimally k-connected matroid, 593
• minimally k-edge-connected graph, 206
• minimum s-t cut, 1077
• minimum t-degree, 322
• minimum-dominating-set (in a cograph) algorithm, 1058
• minimum-convex-cost flow, 1097
• minimum-cost circulation, 1088
• minimum-cost flow, 1088
• minimum-cost-flow problem, 137
• minimum-cost maximum-flow with gains, 1100
• minimum-cost transshipment, 1090
• minimum crosscap imbedding, 618
• minimum crosscap number, 618, 626, 643
• minimum degree of a digraph, 198
• minimum degree of a graph, 196
• minimum edge cover of a graph, 899
• minimum genus (of a graph) 26, 618, 625, 642
• minimum genus imbedding, 618
• minimum geodetic set, 877
• minimum geodetic subgraph, 877
• minimum hull subgraph, 878
• minimum nonorientable genus, 643
• minimum spanning tree of a set of points, 1020
• minimum-tolerance interval graph, 915
• minimum triangulation, 742
• minimum-weight cycle-cover problem, 224
• minimum-weight drawable graph, 1019
• minimum-weight drawing, 1019
• minimum-weight forbidden graph, 1019
• minimum-weight triangulation, 1019
• minimum-vertex-cover problem, 390
• minor of a graph, 111, 581, 628, 730, 807
• minor of a matrix, 221
• minor of a matroid, 581
• minor-closed class of matroids, 586
• minor-minimal imbedded graph, 732
• Minty’s Painting Theorem, 549
• mixed-cut, 216
• mixed graph, 6, 970
• mixed hypergraph, 375
• mixed-integer program (MIP), 1118
• mixed version of CPP (MCPP), 237
• M-join in a graph, 442
• model for an axiom system, 766
• monadic second-order logic (MSOL),
• monogon (a one-sided polygon), 673
• monomorphism, 90
• monotone graph property, 805, 818
• Moore bound for a digraph, 310
• Moore bound for a graph, 311
• MSOL’ (set of expressions for a graph), 1061
• multi-arc, 6
• multicommodity flow network, 1084
• multi-edge, 3
• multigraph, 4, 351
• multi-level network design (MLND), 1124
• mutually reachable vertices, 127, 197
• Mycielski graphs, 798