o 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
FourColor
....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
13 Sep 2009
.
© 19992009
Aaron D. Gross
Email the Webmaster


Graph
Theory
Textbooks and Resources

New in
December 2003
zoom cover
Order from
Amazon

Handbook of
Graph Theory
Jonathan L Gross
Columbia University, New York, New York, USA
Jay Yellen
Rollins College, Winter Park, Florida, USA
Series: Discrete Mathematics and Its Applications Volume: 25
Cat. #: 8522
Number of Pages: 1192
ISBN: 1584880902
List Price: $119.95
Publication Date: 12/29/2003 
FEATURES
 Provides a unified, uptodate
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 easytoread algorithms
Includes a glossary in each
chaptermore than 1000 entries in total
PUBLISHER'S DESCRIPTION
The Handbook of Graph Theory is the most comprehensive
singlesource guide to graph theory ever published. Bestselling
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 theoryincluding 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 nonexperts 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 “kcoloring” 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.
Topic, Page(s)
A 
A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 aapproximation algorithm, 979
 aperfect graph, 433
 cbinding function, 352
 D'phase, 1095
 DYtransformation of a triangulation, 732
 ftolerance unit interval graph, 916
 kabsorption, 231
 kdetachment, 231
 ktransformation, 231
 k*transformation, 231
 mfunction (in representativity), 733
 wperfect graph, 433
 2cell imbedding, 618
 2opt 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 st 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, lthorder, 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
 antidirected path, 163
 antifactor set, 409
 antihole, 433
 antisymmetric digraph, 305
 apex graph, 636
 approximate (or approximation)
 algorithm, 246, 281
 r(n)approximation, 379
 aapproximation algorithm, 979
 arborescence, 129
 arboricity, 396, 935
 arboricity, klinear, 414
 arc, 5
 sarc, 493
 arccoloring, proper, 137
 arccoloring lemma, 549
 arccut, 129, 216
 arcdisconnecting set, 129
 arcdisjoint paths, 1090
 Archimedean ötolerance interval graph, 916
 karcstrong digraph, 26
 arctransitive graph, 491
 area of a drawing, 1022
 carrangeable graph, 846
 arrowing a ktuple (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
 Atrail (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
B

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 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
 baramalgamation of two graphs, 643
 1barrier, 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 kopt (for TSP), 288
 BESTTheorem (eulerian tours), 221
 Betti number b(G), 626
 bfs (= breadthfirst search), 953
 BIBD (balanced incomplete block design), 761
 biconnected component of a graph, 967
 biconnected graph, 1016
 bicritical graph (re 1factors), 406
 bicycle, 550
 bicyclebased tripartition, 550
 bidegreed graphs, 84
 bidirectional double tracing, 222
 bifurcated flow, 1120
 bihypergraph, 375
 binary constraint satisfaction problem, 924
 binary mvector, 538
 binary tree, 139, 147, 528, 1016
 binarysearch algorithm, 140
 binarysearch tree, 140
 binding number, 404
 cbinding 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
 BondyChvatal Theorem, 801
 BondyErdos Conjecture (Ramsey numbers), 843
 book (2complex), 617
 rbook (type of graph), 792
 boundary vertices of a subgraph, 991
 boundary of a surface, 611
 boundaryseparating closed curve, 646
 boundarywalk specification, 616
 bounded automorphism, 499
 bounded mintolerance interval graph, 915
 bouquet, 4, 20, 648, 664
 branch points if a branched covering, 669
 branch set of a branched covering, 669
 branchdecomposition of a graph, 105
 branched covering, 669
 branchwidth of a graph, 106
 breadthfirst search, 953
 breadthfirst algorithm, 61, 955
 breadthfirst 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
C

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 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 vehiclerouting problem (CVRP), 292
 capacitated communication facility, 1118
 capacity in a flow network, 1075, 1084
 capacity of an st cut, 1077
 capacity of flowaugmenting path, 1079
 capacityscaling algorithm (for minimumcost 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
 2cell imbedding, see cellular imbedding
 0cell, 1cell, 2cell, 616
 celldistribution vector (fvector), 699
 cellular imbedding, 618, 625, 698, 722
 center of a graph, 16, 875
 center of a strong digraph, 885
 kcenter, 883
 central vertex, 16, 875
 kcentral 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
 childnode 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
 kchoosable 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
 bchromatic number, 371
 kchromatic graph, 342
 Chvatal’s Theorem (for perfect graphs), 437
 ChvatalErdos Theorem, 801
 CIgraph, 509
 CIgroup, 509
 circ (= closed trail), 538
 circlepacking 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
 ClarkeWright savings algorithm (for
 class edgereconstruction number, 85
 class reconstruction number, 85
 Class 1 and Class 2 (for edgechromatic number), 354
 claw, 404
 clawfree closure, 273
 clawfree graph, 84, 404
 clean triangulation, 738
 clique, 389, 431, 1056
 sclique, 789
 clique cover of a graph, 431
 clique cover, fTedge, 918
 clique cover, pedge, 914
 clique hypergraph, 376
 clique incidence matrix, 436
 clique number, 301, 389, 431, 789
 clique partition number, 416
 cliquewidthk graph, 108, 1059
 closed disk, 611
 closedend 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, kdegree, 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
 cocktailparty 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
 kcolorable graph, 7, 342
 Lcolorable graph (list), 343
 colorable hypergraph, 375
 colorclass adjacency matrix, 70
 colorclass size vector, 70
 coloring number of a hereditary property, 805
 coloring number (ErdosHajnal), 345
 coloring of a graph, 70
 coloring, partial, 373
 coloring, total, 352
 lcoloring, 371
 bcoloring, 370
 Hcoloring of, 372
 kcoloring of a graph, 342
 Tcoloring, 371
 colorpreserving 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,ftolerance, 918
 pcompetition graph, 914
 complement (= edgecomplement), 432, 929
 complement of a subgraph in a graph, 534
 complementreducible graphs, 107
 complementarity property for a schedule, 466
 complementarity in mincost network flow, 1091
 complementary numbering, 927
 complementary profiles in scheduling, 464
 Complementary Slackness Theorem, 1091
 complete kary tree of depth d, 926
 complete kpartite graph, 25, 791, 925
 complete mary 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 runiform 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 edgeconnectivity, 320
 Condorcet paradox, 174
 Condorcet winner, 174
 3configuration, 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
 2connected matroid, 583
 3connected matroid, 585
 kconnected graph, 26, 196, 263, 789
 connection set for a Cayley graph, 22, 505
 connectivity requirement (in a communications network), 1127
 connectivity, tdistance, 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 2complex, 616
 constraint graph, 924
 construction heuristic, 397
 continuous model for mincost flow, 1097
 contractible curve on a surface, 614, 723
 contractible edge in triangulation, 744
 kcontractible edge, 204
 kcontractible 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
 kcore of a graph, 824
 corona of two graphs, 894, 931
 correctness property of drawing checker, 1034
 coset of a subgroup, 318
 cospanning tree (= cotree), 536, 629
 cost chromatic number, 372
 cost flow network, 137
 cost of a coloring, 372
 cost set for coloring, 372
 cotree, 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 kchromatic, 26, 346
 critically kconnected, 26
 critically kedgeconnected, 26
 critically nconnected, 207
 kcritically nconnected, 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
 dcube 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
 cutedge, 14, 195
 cut matrix, 546
 cut orientation, 545
 cut vector, 542, 545
 cutvertex, 14, 195
 st 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
 cyclecanceling algorithm (for minimumcost flow), 1092
 cycle cover, 224
 cycle decomposition, 215
 cycledecomposition transition system, 227
 cycle double cover, 224
 cycle doublecover conjecture, 224, 699
 cycle extendable, 266
 cycle flow, 1099
 cycle graph, 20
 cycle packing, 224
 cycle rank, 24, 626, 654
 cycleshift, of a bitstring, 253
 cycleshift 2factor, 254
 cycleshift arc, 254
 cyclic bandwidth, 936
 cyclically kedgeconnected, 354
 cylinder, 612
D

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 DAG (directed acyclic graph), 142, 960
 daisy (= subdivided bouquet), 895
 dead end of a dfs path, 968
 deBruijn 2factor, 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, Srelative, 259
 decision tree, 175
 deck for reconstruction, 79
 decomposable into complete subgraphs, 902
 Hdecomposition 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
 ddegenerate 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
 depthfirst forest, 59, 956, 957
 depthfirst search, 956
 depthfirst search algorithm, 60, 958
 depthfirst 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 (depthfirst search), 956
 dfs tree, 956
 diagonal flip, 748
 Pdiagonal flip, 751
 diagramtracing puzzles, 30
 diameter, 10, 301, 874, 934, 954
 diameter of a strong digraph, 884
 kdiameter, 882
 digon (= 2sided 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 edgeset, 195
 disconnecting vertexset, 129, 195
 disconnecting set, 129
 (uv)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
 distanceregular, 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
 doublyperiodic graph, 379
 doublyregular tournament, 158
 drawable as a minimum spanning tree, 1020
 drawing checker, 1034
 hvdrawing (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
E

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 ear, 627
 ear, attaching a closed, 654
 ear, attaching an open, 654
 ear decomposition, 627, 973
 ear decomposition, 3connected,
628
 ears, serially attached, 655
 Eberhard’s Theorem, 700
 eccentricity, 10, 873, 884
 2ECSS algorithm, 979
 keccentricity, 882
 kECSS, 979
 edge of a graph, 2
 edge, proper, 3
 edge of a map, 696
 edgeautomorphism, 487
 edgebandwidth, 937
 edge choice number, 352
 Edmonds’s Branching Theorem, 977
 Edmonds’s Theorem (for general
 edgechromatic number, 7, 449, 934
 edge clique cover, 910
 cedgecolorable, 7
 edgecoloring, 7
 edgecoloring, proper, 351, 374,
449
 kedgecoloring, 838
 edgecomplement, 14, 432
 edgecomplement of a subgraph, 534
 kedgeconnected graph, 26, 196,
223, 979
 edgeconnectivity, 25, 129, 195,
197, 223, 304
 tdistance edgeconnectivity, 321
 edgecontraction, 111, 703
 edgecut, 129, 195, 216
 edgedeck for reconstruction, 79
 edgedeleted subgraph for one
edge, 79
 edgedeletion subgraph for subset
of
 edges, 195
 edgedensity model, 270
 edge design, 1119
 edge difference polynomial, 344
 edgedisconnecting set, 129
 edgeextraction, 111
 edgeface equality, 631
 edgeface inequality, 631
 edge fiber for a voltage graph,
663
 edgegroup, 487
 edgeisomorphism, 487
 edgemultiplicity, 3
 edgenumbering, 936
 edgerecognizable class of graphs,
83
 edgereconstructible class of
graphs, 80
 edgereconstruction conjecture, 80
 edgereconstruction number, 85
 edgereconstruction of a graph, 80
 kedgereconstruction, 91
 (uv)edgeset, 321
 edgesum, 936
 edgesymmetric, 316
 edgetransitive, 12, 316, 416, 491
 edgewidth of a graph imbedding,
697, 723
 Edmonds’s Branching Theorem, 977
 Edmonds’s Theorem (for general
matching), 1112
 eigenvalues of a graph, 557
 eigenvaluesdiameter (lower)
bound, 560
 elementary figure, 559
 elementary graph, 89
 empty graph, 20, 534
 endequivalent rays, 496
 endomorphism, 496
 endoskeleton of a triangulation,
1019
 endpoints of an edge, 2
 endvertexdeck for reconstruction,
85
 equivalent triangulations under
diagonal flips, 748
 equivalent triangulations under
homeomorphism, 753
 equivalent panel structures, 755
 YDYequivalent
triangulations, 732
 Erdos conjecture (about
tournaments), 170
 Erdos–Faber–Lovasz conjecture, 350
 ErdosRenyi graph, 797
 ErdosRenyi random graph, 818
 ErdosSos conjecture, 799, 843
 ErdosStone Theorem, 795
 ES (algorithm for postman
problem), 247
 essential cycle in a graph
imbedding, 615, 747
 aessential
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
 euleriantourtype algorithms,
233, 240, 242, 245, 247, 249
 eulerian trail, 9
 eulerian triangulation, 726
 eulerian graph, 26, 215, 238
 euleriantour transition system,
227
 even component, 629
 even vertex on an alternating
path, 1111
 even graph, digraph, or mixed
graph, 215,
 evensymmetric, 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
F

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 face of a 2complex, 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
 facesize sequence (psequence) of
a map, 699
 facetracing algorithm, 621
 facewidth of a map, 697
 facewidth 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
 1factor, 404, 1103
 [a, b] factor, 410
 (g, f)factor, 411
 ffactor, 409
 Ffactor, 413
 Gfactor, 416
 Gfactor recognition problem, 416
 Hfactor, 793
 kfactor, 21, 265, 403, 408
 rfactor in timetabling, 463
 factorization, 403, 512
 dfactorization 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
 fiberpreserving homeomorphism,
670
 algorithm, 1081
 fiber in a graph covering, 663,
669
 final vertex of a walk, 9
 finishtime order of a search, 959
 finite affine plane, 762
 finite automaton, 64
 finite geometry, 761
 finite projective plane, 762
 firstmoment method, 860
 Five Color Theorem, 367
 fixed cost in communication
network, 1118
 fixed parameter tractable problem,
1036
 fixedsize model, 270
 flag, 706, 709
 flat in a matroid, 577
 Fleury’s algorithm (eulerian
tours), 218
 2flip (= Whitney flip), 728
 flow, 225, 1119
 st flow, 1088
 flow across cut, 1078
 flowaugmenting path, 1079
 Flow Augmentation Theorem, 1079
 flow decomposition, 1099
 flow graph, program, 974
 flow over time, 1098
 flow with gains, 1100
 flow, standard 1088
 FloydWarshall (allpaths)
algorithm, 63
 forbidden graphs, 790
 forbidden minors, 112
 FordFulkerson (maximum flow)
algorithm, 1081
 forest, 16
 forest, klinear, 414
 forward arc (for spanning tree),
1077, 1090
 forward edge (for spanning tree),
59, 956
 fourcolor problem, 39
 Four Color Theorem, 367, 702
 FPT class, 1036
 fractional chromatic number, 365
 fractional vertexcoloring, 365
 free edge for a matching, 1103
 free vertex for a matching, 1103
 free action of an automorphism
group,
 Hfree (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
G

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Gabriel graph, 1020
 gain factor, 1099
 gain network, 1099
 gainy arc, 1100
 gaswaterelectricity problem, 37
 GEM (graph encoded map), 708
 general graph, 4
 generalized pcycle, 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
 sgeodetic digraph, 322
 geometric multiplicity, 558
 geometric realization, 699
 geometry, 761
 geometry of Desargues, 763
 geometry of Pappus, 763
 geometry, npoint, 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

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Hdecomposition 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
 halfedges, 620
 halftransitive graph, 491
 Halin graph, 102
 Hall’s Theorem, 407, 1107
 Hamilton decomposition, 512
 hamiltonconnected graph, 261,
323, 511
 hamiltonlaceable graph, 511
 hamiltonian cycle, 160, 261
 hamiltonian decomposition, 269
 hamiltonian graph, 26, 31, 261,
800
 hamiltonian graph, kordered, 266
 hamiltonian path, 160
 Hamming distance, 391
 Hamming graph, 391, 565
 harmonious coloring, 371
 Hasse diagram, 150
 kHB (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
 kHB (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
 hvdrawing (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
I

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 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
 inarcs of a cut, 216
 inbranching 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
 incidencepartition system, 227
 incident faces of a map, 708
 incident, 2, 708
 increasable flow, 1079
 increasing property, 818
 incremental, 986
 indegree 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
 independentset cover, 432
 independentset 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
 ineccentricity, 322
 infinite connectivity, 499
 initial vertex of a walk, 9
 inscore, 157
 inserting a new edge into an
imbedding, 627
 inset, 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
 internallydisjoint paths, 197
 intersection graph for subsets,
439, 910
 pintersection graph, 914
 intersection graph, ftolerance,
914
 intersection number, 910
 pintersection number, 914
 interval graph, 439, 911
 interval graph, ftolerance
proper, 916
 interval model, 439
 intree (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
 isomorphismcomplete problem, 74
 isomorphism invariant, 11
 isomorphism of labeled graphs, 68
 isomorphism of matroids, 575
 isomorphism of permutation groups,
487
 isomorphism, 68
 isotopic, 738
J  K

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 jackknife operation, 100, 124,
1050
 jellyfish pseudosurface, 612
 Johnson graph, 565
 join operation on two graphs, 14
 joining two vertices, 2
 2join in a graph, 442
 kappa transformations (for
eulerian tours), 231
 KeplerPoinsot regular star
polyhedra, 710
 kernel for a surface, 733
 key (type of graph), 895
 kflow (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 EdgeColoring Theorem, 417
 Konig’s Theorem (edgechromatic
number), 450
 Konig’s Theorem (vertexcover and
matching), 407, 1107
 Konigsberg Bridges Problem, 29,
214
 Kotzig’s Theorem, 969
 Kuratowski graphs, 37
 Kuratowski’s Theorem, 554, 628
L

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 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 edgewidth imbedding, 697,
728
 lattice graph, 563
 layered (di)graph, 1016
 layered drawing, 1017
 leaf generated representation, 917
 leaf, 147
 kleafconnected graph, 323
 left (right) subtree of a binary
tree, 139
 left child in a binary tree, 139,
147
 leftright 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
 LEWimbedding, 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
 klinked graph, 202
 list assignment, 343
 list chromatic index, 352
 list chromatic number, 343
 listL 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
 LovaszWoodall 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
M

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 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
 MaxFlow MinCut Theorem, 1079
 maximal run in a binary sequence,
258
 maximally connected digraph, 198
 maximally connected graph, 196
 maximally distant trees, 550
 maximally edgeconnected digraph,
198
 maximally edgeconnected graph,
196
 maximum clique, 460
 maximumclique (in a cograph)
algorithm, 1057
 maximumclique problem, 389
 maximum crosscap imbedding, 618
 maximum crosscap number, 618, 626,
643
 maximum density of a graph, 821
 maximum st flow over time, 1098
 maximumflow characterization,
1079
 maximumflow problem, 137, 1076,
1089
 maximum flow with gains, 1100
 maximum genus imbedding, 618
 maximum genus, 618, 626, 642
 maximumindependentset problem,
389
 maximumindependentset (in a
cliquewidthk graph) algorithm, 1060
 maximumindependentset (in a
cograph) algorithm, 1057
 maximumindependentset (in a kHB
graph) algorithm, 1062
 maximumindependentset (in a
seriesparallel graph) algorithm, 1051
 maximumindependentset (in a
tree) algorithm, 1048
 maximumindependentset (in a
treewidthk graph) algorithm, 1053
 maximumweightindependentset
problem, 390
 maximummatching (in a bipartite
graph) algorithm, 1109
 maximummatching (in a cograph)
algorithm, 1058
 maximummatching (general)
algorithm, 1112
 maximummulticommodityflow
problem, 1084
 maximum nonorientable genus, 643
 maximum number of bends of a
polyline drawing, 1022
 maximumsize matching, 1103
 maximumtolerance interval graphs,
915
 maximumweight bipartite matching,
1090
 maximumweightclique problem, 390
 maximumweight cyclepacking
problem, 224
 maximumweightindependentset
problem, 390
 maximumweightindependentset (in
a tree) algorithm, 1049
 maximumweight matching, 1103
 maximumweight 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/5minimal graph, 895
 minimal polynomial, 560
 minimal triangulation, 704
 minimally kconnected graph, 206,
593
 minimally kconnected matroid, 593
 minimally kedgeconnected graph,
206
 minimum st cut, 1077
 minimum tdegree, 322
 minimumdominatingset (in a
cograph) algorithm, 1058
 minimumconvexcost flow, 1097
 minimumcost circulation, 1088
 minimumcost flow, 1088
 minimumcostflow problem, 137
 minimumcost maximumflow with
gains, 1100
 minimumcost 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
 minimumtolerance interval graph,
915
 minimum triangulation, 742
 minimumweight cyclecover
problem, 224
 minimumweight drawable graph,
1019
 minimumweight drawing, 1019
 minimumweight forbidden graph,
1019
 minimumweight triangulation, 1019
 minimumvertexcover problem, 390
 minor of a graph, 111, 581, 628,
730, 807
 minor of a matrix, 221
 minor of a matroid, 581
 minorclosed class of matroids,
586
 minorminimal imbedded graph, 732
 Minty’s Painting Theorem, 549
 mixedcut, 216
 mixed graph, 6, 970
 mixed hypergraph, 375
 mixedinteger program (MIP), 1118
 mixed version of CPP (MCPP), 237
 Mjoin in a graph, 442
 model for an axiom system, 766
 monadic secondorder logic (MSOL),
 monogon (a onesided 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
 multiarc, 6
 multicommodity flow network, 1084
 multiedge, 3
 multigraph, 4, 351
 multilevel network design (MLND),
1124
 mutually reachable vertices, 127,
197
 Mycielski graphs, 798
N

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 NashWilliams’s Lemma, 91
 natural action on a Cayley graph,
685
 natural automorphism of a covering
graph, 666
 natural projection onto a voltage
graph, 663, 673
 nearregular tournament, 158
 near triangulation, 713
 nearestneighbor algorithm (for
TSP), 284
 nearest vertex insertion (NVI),
286
 Nebesky nuinvariant, 630
 necklace of type (r, s), 633, 654
 necklace (class of binary
strings), 257
 negative afragment, 315
 negative boundary of a vertex
subset, 314
 negative edgeboundary, 315
 negative fragment, 315
 neighbor of a vertex, 2
 neighborhood of a vertex in a
digraph, 157, 263
 neighborhood of a vertex in a
graph, 70
 neighboring clusters, 991
 neighborhood complex of a graph,
344
 neighborly polyhedral map, 703
 nest of contractible cycles, 723
 net voltage on a walk, 665, 742
 network, 1117
 network, st flow, 137, 1087
 network, (standard) flow, 1087
 network design problem, 1118
 network loading problem (NLP),
1130
 network reliability, 222
 nil pointer in a linked list, 58
 kNLC (nodelabelcontrolled)
graph, 109
 noclashes constraint, 448
 node, 2, 71
 nodecoloring, proper 453
 node kcoloring, proper, 453
 nodelabelcontrolled graph (NLCgraph),
109
 node levels, 1128
 nonbifurcated, 1120
 nonconnected, 194
 nondeterministic finite
automaton, 64
 nonintersecting, 229
 nonleaf node, 71
 nonorientable genus, see crosscap
number
 nonorientable genus of a surface,
614, 692
 nonorientable genus of an
imbedding, 625
 nonorientable genus of a group,
692
 nonorientable surface, 614
 nonrevisiting path in a map, 714
 nonsaturating flow operation,
1096
 nonseparating cocircuit in a
matroid, 593
 nonseparating curve on a surface,
614
 nontree edge, 16, 956
 nontree vertices, 16
 NordhausGaddumtype results, 900,
929
 normal form of a matrix, 552
 nowherezero 5flow conjecture,
225
 nowherezero kflow, 369
 nowherezero flow, 225
 NPcomplete problem, 924
 nth power of a graph, 434
 null graph K0, 4, 20, 534
 nullity (see cycle rank), 536
 stnumbering of a graph, 973
O

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 octahedral graph, 22
 odd component of a cotree, 629
 odd vertex on an alternating path,
1111
 oddcycle property, 404
 (1, f)oddfactor, 410
 online coloring, 373
 open disk, 611
 open ear decomposition, 973
 open face, 722
 open neighborhood of a vertex,
394, 890
 open neighborhood of a vertex
subset, 892
 open walk, 9
 openlydisjoint (= internally
disjoint), 197
 orthocenter of a triangle, 763
 orthodox (h, s, t)representation,
917
 orthogonal complements of a vector
space, 543
 kopt algorithm for TSP, 288
 eoptimal
pair, 1096
 orbit of an edge, 12
 orbit of a vertex, 12
 order of an edge in a branch
decomposition, 105
 order of a graph (= number of
vertices), 262
 order of a group, 487
 order of a tournament, 156
 ordertype (re algebra), 509
 orderedpair permutation, 520
 ordered tree, 139, 147, 528, 955
 Ore’s Theorem (for dominating
sets), 891
 Ore’s Theorem (for hamiltonian
graphs), 801
 orientable imbedding number of a
graph, 642
 orientable surface, 614
 orientable cycle double cover, 224
 orientationpreserving group
action, 685
 orientationreversing closed
curve, 615
 orientation of a graph, 967, 970
 oriented dcoloring, 462
 oriented boundary walk, 616
 orientedcycle doublecover
conjecture, 224
 oriented graph, 131, 305
 oriented polygon, 616
 oriented 2complex, 616
 origin node of a communication
network, 1118
 orthogonal drawing, 1016
 orthogonal eulerian tour, 227
 orthogonal representation, 1016
 orthogonal subspaces of a vector
space, 542
 Otter’s formula (for rooted
trees), 525
 outeccentricity, 322
 outarcs of an arccut, 216
 outbranching (= outtree), 169
 outdegree, 8, 57, 157
 outer vertex (re domination), 896
 outerplanar graph, 229, 367
 outset of a vertex of a digraph,
157, 913
 outtree, 129, 146, 169, 220
 overlap matrix, 650
P

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 packing (in a graph), 899
 packing number of a graph, 899
 painting of a digraph, 549
 pairpermutation, 517
 Paley graph, 506
 pancyclic graph, 266, 802
 panel, 755
 panel structure, 755
 Pappus’s Theorem, 763
 parallel computation network, 924
 parallel elements of a matroid,
577
 parallel operation, 100, 124, 1050
 parent in a rooted tree, 139, 147
 kparitylinked graph, 202
 partial ordering, 149
 partially balanced incomplete
block design, 761
 partially directed graph (= mixed
graph), 6
 partially dynamic graph problem,
986
 partially ordered set, 150
 kpartite graph, 25, 301
 partite sets, 24, 25
 partition number, 431
 partitioncut for a vertex subset,
216
 pasting topological spaces
together, 616
 path, 9, 57
 Apath, 199
 A–B path, 199
 kpath, 163
 uvpath, 963
 path degree sequence matrix, 71
 path factor, 413
 path flow, 1099
 path graph Pn, 20
 path layer matrix, 71
 pathdecomposition, 105
 kpaths problem, 202
 pathwidth, 105
 PBIBD (partially balanced
incomplete block design), 761
 penalty weight in timetableing,
453
 perfect communication channel, 434
 perfect difierence set, 764
 perfect elimination ordering, 912
 perfect graph, 101, 433
 aperfect
graph, 433
 Perfect Graph Theorem, 433
 perfect matching, 239, 404, 463,
967, 1103
 perfect matrix, 436
 peripheral vertex of a graph, 875
 periphery, 875
 permanent, 407
 permutation graph, 440
 permutation scheme on a finite set
X, 708
 permutation scheme of a map, 708
 permutation voltage assignment,
667
 permutation voltage graph, 667
 permutation voltage group, 667
 Perron root, 394
 PERT (program evaluation review
technique), 43
 Petersen graph, 23, 42
 Petersen’s Theorem (1factors),
405
 phase transition for random
graphs, 824
 phase of a flow algorithm, 1095,
1096
 pinched open disk, 611
 pinched torus, 612
 pivotvertex (for isomorphism
testing), 71
 placement problem for VLSI design,
923
 planar (di)graph, 1017
 planar drawing, 1016
 planar graph, 26, 628
 planar matroid, 579
 Planar Separator Theorem, 715
 planarizing collection for an
imbedding, 731
 planarizing curve for a nonplanar
region, 646
 planarizing orders for an
imbedding, 729
 plane graph, 367
 Platonic graph, 23
 Platonic solids, 23, 710
 points of a geometry, 761
 polygonal complex, 616
 polyhedral map, 697
 polyhedral imbedding, 722
 polyline drawing, 1016
 polynomial algorithm, 924
 polynomial deck, 87
 polynomial growth of degree n, 491
 poset, 150
 positive
afragment, 315
 positive boundary, 314
 positive edgeboundary, 315
 positive fragment, 315
 postman problem, 237
 postman tour, 138, 222, 237
 postman tour, open, 238
 postorder of a graph search, 959
 kth power of a cycle, 798
 kth power of a graph, 265, 927
 precoloring extension problem, 373
 preflow, 1081
 preflowpush algorithm, 1082
 preorder of a graph search, 959
 PrExt (precoloring extension), 373
 primaldual algorithm (for
minimumcost flow), 1094
 prime, under a product operation,
489
 primitive permutation group, 495
 principal partition, 551
 principal subgraph, 551
 principal submatrix, 561
 product, cartesian, 14
 profile of a proper numbering, 937
 profile of a graph, 937
 profile width, 937
 profile of a team, in scheduling,
464
 projective plane, 613
 proper divisor, under a product
 proper numbering, 923
 proper coloring, 7, 342
 proper minor, 581
 property Ak for reconstructability,
81
 proportional cost structure, 1124
 proximity graph, 1020
 proximity region, 1020
 pseudomanifold, 612
 pseudominimal triangulation, 750
 pseudosurface, 612
 punctured surface, 751
 push(v,w) operation, 1096
 pushrelabel algorithm (for
minimumcost flow), 1094
Q

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 quadrangulation, 726, 756
 quadratic residue tournament, 158
 quality of a timetabling solution,
458
 quasi 4connected graph, 309
 quasiminimal connection set, 511
 quickly recognized membership in a
class, 112
R

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Rodl nibble, 864
 Redei’s Theorem, 970
 radial graph, 723
 radio coloring, 371
 radius, 10, 874, 884, 934
 kradius, 882
 Ramsey graphs, 851
 Ramsey multiplicity, 853
 Ramsey number, 838, 861
 Ramsey number, generalized, 838
 Ramsey number, khypergraph, 853
 Ramseyfinite pair, 851
 Ramseyinfinite pair, 851
 Ramsey’s Theorem, 837
 RamseyTuran problems, 807
 random digraph, kin, lout, 270
 random graph, binomial, 412, 817
 random graph, uniform, 818
 random vertex insertion (for TSP),
286
 randomness of an infinite binary
sequence, 258
 rank of a matroid, 577
 rank of a subset in a matroid, 577
 rankr whirl, 588
 rank of a graph, 536
 rank of an abelian group, 691
 ranking number for colorings, 373
 trational graph, 416
 tRational Recognition Problem,
416
 ray, aessential, 500
 reachability trees, 1003
 realizing a topological space, 616
 receiver vertex in a tournament,
157
 recognizable class of graphs, 83
 Nreconstructible digraph, 93
 reconstructible graph parameter,
82
 reconstructible graph, 80
 reconstruction conjecture, 80
 reconstruction index, 92
 reconstruction number, 85
 reconstruction of a graph, 80
 rectangle of influence graph, 1020
 recursively constructed graph
class, 99, 1046
 redblue edgecoloring, 861
 Redei’s Theorem, 970
 reduced cost vector, 1091
 reduced digraph, 1015
 reduced incidence matrix, 546
 reduced tree, 524
 reducible arc (re flow), 1079
 reducible tournament, 157
 reducible flow graph, 975
 rreducible
subgraph, 205
 reduction operations, 113
 refinement of a graph coloring, 70
 refinement (see subdivision), 926
 regular expressions, 64, 65
 regular graph, 21
 kregular graph, 21
 sregular graph (algebraically),
493
 regular map, 709
 regular matrix, 553
 regular permutation group, 493,
506
 regular sets, 66
 regular tournament, 158
 related vertices in a rooted tree,
956
 relation on a set, 134
 relatively prime graphs, 489
 (h, s, t)representation of a
graph, 917
 krepresentative imbedding, 738
 representativity, 723
 reservation in communication
networks, 1134
 residual capacity, 1079, 1090
 residual network, 1079, 1090
 residue type w.r.t. a modulus, 509
 resource slot for timetabling, 447
 restricted partition of a tree,
988
 restriction of a matroid, 581
 retracing in a walk, 223
 retractfree walk, 223
 reverse direction, 616
 reverse of a trail, 231
 RiemannHurwitz equation, 687, 688
 right child in a binary tree, 139,
147
 rim, 588
 ring sum, 538
 (r, k)configuration, 762
 Robbins’s Theorem, 131, 969
 RobertsonSeymour Theorem
(excluded minors), 587
 robustness in a graph drawing
checker, 1034
 root systems (in spectral graph
theory), 563
 root of a tree, 71, 129, 145, 1016
 rooted imbedding, 728
 rooted tree, 99, 129, 145, 523,
1016
 rotation at a vertex, 620
 rotation of a binary string, 257
 rotation scheme of a map, 707
 rotation, global, 621
 rotational tournament, 158
 roundrobin tournament, 462, 520
 run in a binary string, 258
 runpermuted sequence, 258
 rural postman problem, 238
S

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Sabidussi’s Theorem (for Cayley
graphs), 506
 same direction of edges, 549
 same relative orientation of an
edge, 547
 saturated arc set, 1090
 saturating an arc, 1089
 saturating operation, 1096
 Xsaturating matching, 1106
 saving of a merger of cycles, 293
 savings digraph, 293
 scanned from a vertex in a search,
958
 score, 157
 score sequence or score vector,
157
 SE (= symmetric even), 248
 search of a graph, 953
 second neighborhood, 166
 seg (see cut), 538
 segment reversal of an eulerian
tour, 231
 segment of an eulerian tour, 231
 segments (w.r.t. a subgraph), 971
 selfcentered graph, 876
 selfhealing rings in networks,
1134
 selfloop, 3
 selfunion of a graph, mfold, 15
 semicellular graph imbedding, 645
 semidominator, 977
 semigirth, 306
 psemigirth of a digraph, 312
 semiregular factor, 410
 semisymmetric graph, 491
 separating two subsets, 199
 separation of two rays by a
subgraph, 496
 separating a surface by a closed
curve, 614
 separation pair in a 2connected
graph, 973
 serf vertex in a tournament, 168
 series operation, 100, 124, 1050
 seriesparallel graph, 100, 1050
 set edgereconstructible, 87
 set reconstructible, 87
 set reconstruction conjecture, 86
 set representation of a graph, 910
 (uv)set, 198, 321
 setmerging problem, 975
 Seymour’s Theorem (for regular
matroids), 586
 Shannon capacity, 434
 shape of a set in a drawing, 1021
 sharp threshold function, 820
 shattering a color class, 71
 shift operation on a bitstring,
253
 shortcuts in TSP, 286
 shortestpath tree, 954
 shrunken blossom, 1111
 siblings in a rooted tree, 147
 signature (= orientationreversing
edges), 621
 signed boundary walk, 616
 signed edges, 616
 similar imbeddings, 732
 simple adjacency, 3
 simple digraph, 6
 simple graph, 3
 simple matroid, 577
 simple polyhedral map, 699
 nsimplex, 23
 simplicial map, 699
 simplicial vertex, 440, 912
 simplicity of a graphdrawing
checker, 1034
 simulated annealing, 460
 sincere decision in voting, 175
 singlesource shortest paths, 1089
 singlesource singlesink network,
1087
 sink vertex of a digraph, 142,
960, 1016
 sink of a flow network, 137, 1075
 size of a book, 792
 size of a face, 631
 size of a graph (= E(G)), 262,
898
 size of a matching, 1103
 size Ramsey number, 838
 size Ramsey number, restricted,
851
 skeleton of an imbedding, 737
 skeleton of a complex, 22, 616
 1skeleton, 22
 skew partition of the vertices of
a graph, 442
 skew vertex in a triangulation,
754
 smoothing a 2valent vertex, 635
 snark, 354
 soft constraint, 448
 software testing, 137
 sophisticated decision, 176
 source vertex of a digraph, 1016
 source in a flow network, 137,
1075
 source in a digraph, 142, 960
 spanning kwalk, 727
 spanning cycle, 160
 spanning forest, 536
 spanning path, 160
 spanning set, 577
 spanning subgraph, 13
 spanning subgraph, smallest
bridgeless, 979
 spanning tree, 16, 536
 spanning walk, 727
 sparse graph, 57, 994
 specification of a fundamental
polygon, 617
 spectrum of a graph, 557
 sphere, 612
 nspike matroid, 588
 spiked cycle (type of graph), 171
 spindle pseudosurface, 612
 spine of a book, 617
 splicing eulerian trails, 231
 ab split of a graph at a vertex,
218
 splitting a face by edge
inserting, 627
 splitting a face by edge deletion,
628
 splitting algorithm, 220
 splitting lemma, 219
 splitting operation on eulerian
trails, 218
 splitting a vertex, 204
 splittingclosed class of
triangulations, 751
 spoke matroid, 588
 square of a cycle, 798
 square of a graph, 352
 stdigraph, 1016
 stabilization of a coloring, 70
 stabilizer subgroup of
permutations, 491
 stable set (= independent set),
453, 465
 stable coloring (in isomorphism
testing), 70
 kstable tournament, 168
 stacker crane problem, 239
 standard plane representation of
an ordered tree, 139
 standard random graph process, 830
 standard simplex, 392
 standard triangulation on the
sphere, 748
 standardized random variable, 819
 star neighborhood in a
triangulation, 738
 start vertex in a program flow
graph, 974
 stationary Markov process, 133
 status (= total distance), 880
 Steiner distance, 882
 Steiner nodes, 1125
 Steiner tree problem, 1125
 Steiner tree, 882
 Steiner triple system, 761
 Steinitz’s Theorem, 701
 straightline drawing, 1016
 straightness of a double ray, 500
 stratified graph, 657
 jth stratum, 657
 strength of a graph, 372
 strict kcoloring of a mixed
hypergraph, 375
 strictly balanced graph, 821
 strip, 499
 strong center, 886
 strong central vertex, 886
 strong component (SC), 128, 964
 strong component algorithm, 964
 strong component graph (=
condensation), 964
 Strong Cycle Double Cover
Conjecture, 224
 strong diameter, 885
 strong digraph, 160, 884
 strong double tracing, 223
 strong eccentricity, 885
 Strong Imbedding Conjecture, 699
 Strong Perfect Graph Theorem, 433
 strong product, 269, 489, 932
 strong radius, 885
 strong (Steiner) distance, 885
 strong symmetric genus, 685
 strong tournament, 520
 kstrong digraph, 26, 163
 strongly karcconnected, 26
 strongly kconnected, 26, 163
 strongly cellular imbedding, 618
 strongly connected digraph, 10,
128, 160, 197, 238, 884, 964
 strongly connected tournament, 520
 strongly geodetic, 322
 strongly noncellular imbedding,
645
 strongly noncontractible closed
curve, 646
 strongly orientable graph, 131
 strongly polynomial algorithms
(for minimumcost flow), 1097
 strongly regular graph, 566
 (n, k; a, c)stronglyregular
graph, 319
 strongly selfcentered digraph,
886
 strongly symmetric imbedding, 685
 strongly unimodal sequence, 653
 structure (in reconstruction), 91
 STSP (= Symmetric TSP), 279
 subdivision of an edge, 926
 subexponential growth of a
function, 491
 subgraph, 534
 kregular Subgraph Recognition
Problem, 419
 subtree graph, 912
 successor of a substring, 253
 sum (= join), 930
 1sum of matroids, 582
 2sum of two 2connected matroids,
585
 3sum of matroids, 585
 sumtolerance interval graphs, 915
 Sumner’s conjecture (about
tournaments), 169
 superk,
305
 superl,
303, 305
 superuniform pair, 803
 surface minor, 730
 surface rotation at a vertex, 621
 surface with k holes, 614
 surface, 612
 survivable network, 1127
 suspension operation, 14
 sweepingheuristic algorithm (for
vehicle routing), 295
 switch installation cost, 1118
 switch (in communication network),
1118
 switches (in an imbedding), 621
 symbol set of a rotational
tournament, 158
 symmetric Euler genus, 692
 symmetric configuration, 762
 symmetric crosscap number, 692
 symmetric difierence, 538
 symmetric digraph, 238
 symmetric digraph, associated, 197
 symmetric genus, 685
 symmetric group, 318, 516
 symmetric imbedding, 685, 692
 symmetric mixed graph, 244
 symmetric nonorientable genus, 692
 symmetric ordered pair group
Sn[2], 520
 symmetric pair group
Sn(2), 517
 symmetric property (of a metric),
874
 Symmetric TSP, 279
 symmetric vertex in a digraph, 238
 symmetric vertex in a mixed graph,
244
 symmetrical map, 709
 symmetriceven approach to postman
problem, 248
 symmetry group of an imbedding,
753
 symmetry (= automorphism), 753
 system of imprimitivity, 495
 ksystem that dominates, 265
 SzekeresWilf number, 345
T

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 tabu search, 398, 461
 tail of a directed edge, 5, 127
 target (= sink), 1016
 Tarry’s algorithm, 224
 tensor product, 932
 terminal vertex of a path, 9
 kterminal graph G = (V, T,E), 106
 kterminal recursively structured
class, 106
 terminals, 100, 1050
 tessellation of the sphere or
plane, 705
 thickness of a graph, 935
 threshold function, 820
 tight triangulation, 741
 timetabling algorithm, 468
 timetabling problem, 446
 timetabling problem,
classteacher, 449
 tolerance, 914
 ftolerance
unit interval graph, 916
 top tree (re dynamic graphs), 991
 topological bandwidth, 938
 topological current graph, 674
 topological number algorithms, 961
 topological numbering of a dag,
960
 topological realization of a graph
G, 618
 topological sort or topsort
(algorithm), 151, 960
 topology tree (re dynamic graphs),
988
 torsion subgroup, 497
 torus, 613
 gtorus, 614
 total coloring, 352
 total degree, 244
 total distance td(u), 880
 total edgelength of a drawing,
1022
 total graph T(G) of a graph G, 352
 total imbedding distribution, 650
 totally separating a subset of
vertices, 199
 totally unimodular matrix, 576
 ttough graph, 265
 toughness of a graph, 265, 313,
404
 tour (for TSP), 280
 tour (for TSP), generalized, 289
 ktour (for deBruijn problem), 253
 tournament, 27, 131, 156, 158,
463, 520, 964
 ntournament, 156
 tournament, almost regular, 158
 tournament, kstable, 168
 tournament matrix, 172
 tower of a of length k, 803
 traceable graph (with hamiltonian
path), trail, 9
 DY
transformation of a triangulation, 732
 YDtransformation
of a triangulation, 732
 transit time in a flowovertime
network, 1098
 transition in a cycle
decomposition, 227
 transition in an eulerian tour,
227
 transition matrix for a Markov
chain, 133
 transition probability for a
Markov process, 133
 transition system, 227
 transitive closure algorithm, 64
 transitive closure of a binary
relation, 134
 transitive closure of a digraph,
134
 transitive closure of a graph, 63
 transitive digraph, 134
 transitive edge in a digraph, 1015
 transitive orientation of a graph,
911
 transitive permutation group, 486
 transitive tournament, 161
 stransitive graph, 493
 translation (type of
endomorphism), 497
 transmitter vertex in a
tournament, 157
 transshipment network, 1088
 transshipment network, associated,
1094
 traveling salesman problem (TSP),
42, 279, 280
 traversable mixed graph, 970
 Tree Conjecture (for Ramsey
numbers), 842
 tree distance (between spanning
trees), 550
 tree edges, 16, 59, 956
 tree vertices, 16
 tree, 16, 536
 tree, inductive definition, 24
 trees, chemical, 34
 ktree (= a tree of Kk’s), 101
 mary tree, 147
 rtree (= a tree rooted at r), 976
 14 tree, 527
 treedecomposition, 104, 1053
 treegrowing algorithm, basic, 17
 treegrowing algorithm,
edgeprioritized, 18
 treewidth, 104, 1053
 triangle group, 688, 705.
 triangle inequality, 280, 874
 triangular graph, 563
 triangular imbedding, 737
 triangulated graph (= chordal
graph), 101
 triangulation of a surface, 229,
367, 699, 726, 737
 triangulation of a
surfacewithboundary, 737
 triangulation, kirreducible, 747
 triangulation, kminimal, 704, 748
 Ptriangulation, 751
 triangulation (type of drawing),
1019
 triangulations, Pequivalent, 752
 triconnected graph, 973, 1016
 trivial blocks, 495
 trivial coloring, 70
 trivial disconnecting set of
edges, 303
 trivial graph, 3, 20, 534
 trivial Lyndon necklace, 257
 trivial walk, 9
 ntrivial vertex subset, 320
 strivial edge subset, 320
 TSP (= traveling salesman
problem), 280
 TSP, asymmetric, 279
 TSP algorithms, 284, 286, 287, 294
 TSP, generalized, 289
 Tucker’s algorithm (for eulerian
tours), 233
 Turan graph, 790
 Turan number, 790
 Turantype problem, 790
 Tutte’s Theorem (for 3connected
graphs), 589
 Tutte’s Theorem (for
halftransitive graphs), 491
 Tutte’s 1Factor Theorem, 405
 twist operation on a graph, 576
 type(a) unit (re domination), 895
 type(b) unit (re domination), 895
 type of edge (re orientation), 692
 type of a map, 699
U

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 uncapacitated network design model
(UND), 1122
 uncapacitated network, 1118
 uncolorable mixed hypergraph, 375
 underlying cellular imbedding, 646
 underlying graph of a digraph, 6
 underlying semicellular imbedding,
646
 underlying topological space, 616
 undirected version of CPP (UCPP),
237
 undirected communication facility,
1118
 uniform paths, 1001
 uniform random graph, 818
 euniform
pair, 803
 kuniform hypergraph, 375, 853
 unimodal sequence, 653
 unimodular matrix, 546
 union of matroids, 580
 uniquely kcolorable graph, 348
 uniquely colorable hypergraph, 375
 uniquely edge kcolorable graph,
354
 uniquely hamiltonian graph, 268
 uniquely imbeddable on a surface,
754
 unit cylinder, 612
 unit disk, open, 611
 unit distance (infinite) graph,
357
 unit halfdisk, 611
 unit in a ring, 509
 unit interval graph, 911
 unit sphere, 612
 university course timetabling
problem, 452
 unmatched edges, 1103
 unsplittable flow problem, 1084
 untight triangulation, 741
 update on a dynamic graph, 985
 update algorithms (dynamic), 1006,
1007, 1009, 1010
 upper chromatic number, 375
 upper domination number, 892
 upper irredundance number, 892
 upperimbeddable graph, 628
 upward drawing, 1017
 upward planar digraph, 1017
V

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 valence (= degree), 8
 dvalent vertex, 8
 valid vertex mapping, 107
 value of a flow, 1076
 variable cost, 1118
 vehiclerouting problem, 291
 vehiclerouting algorithms, 294,
295
 vertex of a graph, 2
 vertex of a hypergraph, 68
 vertex of a map, 696
 vertex of a polygonal complex, 616
 vertexcoloring, 7, 341
 vertex kcoloring, proper, 374
 vertexconnectivity, 304
 vertex cover, 389, 406, 1103
 vertex cover number, 406, 935
 kvertexcritical graph, 346
 vertexcut, 129, 195
 vertexdegree sequence
(vsequence), 699
 vertexdeleted (deletion) subgraph,
79, 195
 vertexedge incidence matrix, 562
 vertexface (incidence) graph (=
radial graph), 723
 vertex independence number, 892,
935
 vertexinduced subgraph, 433
 vertexinsertion algorithm (for
TSP), 286
 vertexlabeling, standard, 17
 vertex ranking, 373
 vertex splitting, 703, 744
 kvertexsplitting, 204
 vertexsymmetric, see
vertextransitive
 vertextransitive graph, 12, 316,
486, 506, 685
 vertex variant of a boundary
 specification, 616
 vertexweighted graph, 390
 visibility drawing, 1017
 Vizing’s conjecture, 902
 Vizing’s Theorem, 353
 voltage assignment, regular, 661
 voltage graph, 661, 742
 voltage group, 661, 742
 voltage sequence, 665
 voltage, permutation, 667
 voltage, regular, 661,
 volume of a flow, 1088, 1099
 Voronoi diagram, 1018
W

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Wagner’s Conjecture (solved), 635
 Wagner’s Theorem (for planar
graphs), 628
 walk, 9
 xy directed walk, 127
 walk in a voltage graph, 665
 Warshall’s (transitive closure)
algorithm, graphs), 197, 200
 Whitney’s Theorem (for planar
graphs), 136
 weak duality (for matching), 1105
 weak duality (for network flow),
1078
 weak product, 489
 weakly chordal, 915
 weakly connected digraph, 10, 127
 weakly edgereconstructible, 83
 weakly klinked, 202
 weakly neighborly, 703
 weakly pancyclic, 802
 weakly reconstructible, 83
 weight of a cycle, 224
 weight of a matching, 1103
 weight of a path, 1104
 weight of a set in a matroid, 578
 weight of a vertex set, 390
 weight matrix, 280
 wellbehaved time bound, 994
 wheel graph, 204, 559, 588
 wheelneighborhood, 722
 Whitney 2flip, 728
 Whitney’s Flipping Theorem, 969
 Whitneysimilar imbeddings, 729
 Whitney Synthesis, 627
 Whitney’s Theorem (for kconnected
554
 Whitney’s Uniqueness Theorem, 698
 width of a branch decomposition,
105
 width of an imbedding, 723
 width of a path decomposition, 105
 width of a tree decomposition,
104, 1053
 windy postman problem, 238
 wnpmap (= weakly neighborly map),
703
 word in an alphabet, 221
 wreath product of permutation
groups, 489
X  Y  Z

A B
C D E
F G H
I JK L
M N O
P Q R
S T U
V W XYZ
TOP
 Xuong tree, 629
 YDtransformation
of a triangulation, 732
 YDY
equivalent triangulations, 732
 Zarankiewicz’s problem, 797
 Zemel measure, 281
Back to Top
