Graph Theory Glossary 235163

, ∈R , (u, v) ∈A1 if and only if ( u ', v ' ) ∈A2 ? [GJ79] maximum triangle packing INSTANCE: Graph G = (V, E) . SOLUTION: A triangle packing for G , i.e., a collection V1 , V2 , … , Vk of dist subsets of V, each containing exactly 3 vertices, such that for each Vi = { ui , vi , wi } , 1 ≤ i ≤ k , all three of the edges < ui , vi > , < ui , wi > , and < vi , wi > belong to E . MEASURE: Cardinality of the triangle packing, i.e., the number of dist subsets Vi . [CK00] McCulloch-Pitts neuron A basic building block of neural networks. It receives one or more inputs and produces one or more identical outputs, each of which is a simple non-linear function of the sum of the inputs to the neuron. The non-linear function is typically a threshold or step function which is usually smoothed (i.e. a sigmoid) to facilitate learning. [CERN97] FIGURE

McGee graph The unique 7-cage graph consisting of the union of the two certain subgraphs. It has 24 nodes, 36 edges, and all nodes have degree 3. [EW00] FIGURE

Menger's theorem Minimax characterizations of connectivity by number of pairwise internally-dist or edgedist paths between pairs of vertices. [DW96] meta-heuristic This is a general framework for heuristics in solving hard problems. The idea of "meta" is that of level. An analogy is the use of a meta-language to explain a language. For computer languages, we use symbols, like brackets, in the meta-language to denote properties of the language being described, such as parameters that are optional. Examples of meta-heuristics are: • • • • •

Ant Colony Optimization Genetic Algorithms Neural Networks Scatter Search Simulated Annealing

• •

Tabu Search Target Analysis

Besides parameters that define specific algorithms with each framework, these meta-heuristics also require some concept of representation, which is problem dependent. [HG99] method A particular way of doing something, sometimes also called an algorithm or procedure. [EW00] metric A real-valued symmetric nonnegative binary function that is 0 only when the arguments are equal and satisfies the triangle inequality. [DW96] metric dimension problem Given a graph G = (V, E) and positive integer K ≤ | V | , is there a metric basis for G of cardinality K or less? [GJ79] metric representation An isometric embedding into a Cartesian product. [DW96] Meyniel graph Graph in which every odd cycle of length at least 5 has at least two chords. [DW96] FIGURE

M-graph A graph in which there exist exactly two vertices of odd degree. [WM72] FIGURE

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh |

mi | mj-mz | | n | o | p | q | r | s-so | sp-sz | t | u | v | w | xyz | | minimal | minimum | minimum cut | minimum edge | minimum general | minimum linear | minimum ratio | minimum spanning | minimum vehicle | minor | mincut Let G = G (V, E) be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut C of G is any nontrivial subset of V, and the weight of the cut is the sum of weights of edges crossing the cut. A mincut is then defined as a cut of G of minimum weight. The problem is NP-complete for general graphs, but polynomial-time solvable for trees. [EW00] min-heap property Each node in a tree has a key which is greater than or equal to the key of its parent. [PEB00]

minimal balancing set = minimal deletion set An edge set whose deletion makes the graph balanced but which has no such proper subset. [TZ98] minimal block A graph G is a minimal block if G is a block and for every edge e , the graph G – e is not a block. [CL96] minimal connector problem The problem of forming a tree on n vertices using the minimum number of edges. The solution is given by Kruskal's algorithm. [HC00] minimal cover A minimal cover is a cover for which removal of any single member destroys the covering property. [EW00] minimal cycle Simple cycle induced by the edges of a face. minimal deletion set = minimal balancing set minimal dominating set A dominating set that contains no dominating set as a proper subset. [CL96] minimal imperfect graph Every proper induced subgraph is perfect. [DW96] minimal P-object For a property P, no object of the same type properly contained in this object also has property P. [DW96] minimal spanning tree The spanning tree whose weight is the smallest of all possible spanning trees that you could draw for that graph. [ISEM00] minimally 2-connected Any edge deletion destroys 2-connectedness. [DW96] minimizing dummy activities in PERT networks problem Given acyclic digraph G = (V, A) where vertices represent tasks and the arcs represent precedence constraints and a positive integer K≤ | V | , is there a PERT network corresponding to G with K or fewer dummy activities? [GJ79] minimum attraction radius for binary Hopfield net INSTANCE: An n-node synchronous binary Hopfield network and a stable initial vector of states u∈ {-1, 1}n . A binary Hopfield network is a complete graph where each edge has an

integer weight w(vi , vj ) and each vertex has an integer threshold value t(vi ) . At each time step t each vertex vi has a state x(t, vi ) . x(0, vi ) is given by u and x(t +1, vi ) = sgn (Σ j=1 nw(vi , vj ) - ti ) where sgn is the sign function. An initial vector of states is stable if x(t, vi ) eventually converges for all i . SOLUTION: An initial vector of states v that either converges to a different vector than u or is not stable. MEASURE: The Hamming distance between u and v . If v is the vector nearest to u that does not converge to the same vector as u , then this distance is the attraction radius. [CK00] minimum bandwidth INSTANCE: Graph G = (V, E) . SOLUTION: A linear ordering of V , i.e. a one-to-one function f : V→ {1, 2, … , | V |} . MEASURE: The bandwidth of the ordering max (u, v) ∈ E | f(u) – f(v) | . [CK00] minimum b-balanced cut INSTANCE: Graph G = (V, E) , a vertex-weight function w : E → N , an edge-cost function c : E → N , and a rational b , 0
minimum bounded diameter augmentation INSTANCE: Graph G = (V, E) , positive integer D<|V|. SOLUTION: An augmenting set E' for G , i.e., a set E' of unordered pairs of vertices from V , such that G' = (V, E∪E' ) has diameter D , i.e., the maximum distance of any pair of vertices is at most D . MEASURE: Cardinality of the augmenting set | E' | . [CK00] minimum broadcast time INSTANCE: Graph G = (V, E) and a source node v0 ∈ V . SOLUTION: A broadcasting scheme. At time 0 only v0 contains the message that is to be broadcast to every vertex. At each time step any vertex that has received the message is allowed to communicate the message to at most one of its neighbours. MEASURE: The broadcast time, i.e., the time when all vertices have received the message. [CK00] minimum broadcast time problem Given a graph G = (V, E) , subset V0⊆V and a positive integer K , can a message be broadcast from the base set V0 to all other vertices in time K ? [GJ79] minimum b-vertex separator INSTANCE: Graph G = (V, E) and a rational b , 0 < b ≤ 1/2 . SOLUTION: A partition of V into dist sets A , B , and C , such that max { | A | , | B | } ≤ b⋅ | V | and no edge has one endpoint in A and one in B . MEASURE: The size of the separator | C | . [CK00] minimum Chinese postman problem for mixed graphs INSTANCE: Mixed graph G = (V, A, E) , length l(e) ∈ N for each e ∈ A∪E . SOLUTION: A cycle in G (possibly containing repeated vertices) that includes each directed and undirected edge at least once, traversing directed edges only in the specified direction. MEASURE: The total length of the cycle. [CK00] minimum chordal graph completion INSTANCE: Graph G = (V, E) . SOLUTION: A chordal graph completion, i.e., a superset E' containing E such that G' = (V, E' ) is chordal, that is, for every simple cycle of more than 3 vertices in G' , there is some edge in E' that is not involved in the cycle but that s two vertices in the cycle. MEASURE: The size of the completion | E' – E | .[CK00] minimum clique cover INSTANCE: Graph G = (V, E) . SOLUTION: A clique cover for G , i.e., a collection of subsets V1 , V2 , … , Vk of V, such that

each Vi induces a complete subgraph of G and such that for each edge < u , v > ∈E there is some Vi that contains both u and v . MEASURE: Cardinality of the clique cover, i.e., the number of subsets Vi . [CK00] minimum clique partition INSTANCE: Graph G = (V, E) . SOLUTION: A clique partition for G , i.e., a partition of V into dist subsets V1 , V2 , … , Vk such that, for 1 ≤ i≤ k , the subgraph induced by Vi is a complete graph. MEASURE: Cardinality of the clique partition, i.e., the number of dist subsets Vi . [CK00] minimum color sum INSTANCE: Graph G = (V, E) . SOLUTION: A coloring of G , i.e., a partition of V into dist sets V1 , V2 , … , Vk such that each Vi is an independent set for G . MEASURE: The sum of the coloring Σ 1 ≤ i ≤ k Σ v ∈ Vi i . [CK00] minimum communication cost spanning tree INSTANCE: Complete graph G = (V, E) , weight w(e) ∈ N for each e∈E , requirement r({u, v}) ∈N for each pair of vertices from V . SOLUTION: A spanning tree for G . MEASURE: The weighted sum over all pairs of vertices of the cost of the path between the pair in T , i.e., Σ u, v ∈ V W(u, v) • r({u, v}) , where W(u, v) denotes the sum of the weights of the edges on the path ing u and v in T . [CK00] minimum complete bipartite subgraph cover INSTANCE: Graph G = (V, E) . SOLUTION: A complete bipartite subgraph cover for G , i.e., a collection V1 , V2 , … , Vk of subsets of V, such that each Vi induces a complete bipartite subgraph of G and such that for each edge < u , v > ∈ E there is some Vi that contains both u and v . MEASURE: Cardinality of the complete bipartite subgraph cover, i.e., the number of subsets Vi . [CK00] minimum crossing number INSTANCE: Directed graph G = (V, A) . SOLUTION: An embedding of G in the plane. MEASURE: The number of pairs of edges crossing one another. [CK00] minimum cut The smallest set of edges in an undirected graph which separate two distinct vertices. That is, every path between them includes some member of the set. [PEB00] A network cut having minimum value, or the value of such cut. [DW96] minimum cut cover INSTANCE: Graph G = (V, E) .

SOLUTION: A collection of cuts V1 , V2 , … , Vm , i.e., a collection of subsets Vi⊆V such that, for each edge < u , v > ∈E , a subset Vi exists such that either u∈Vi and v ∉Vi or u∉Vi and v∈Vi . MEASURE: Cardinality of the collection m . [CK00] minimum cut into bounded sets problem Given a graph G = (V, E) , weight w(e) ∈Z+for each e ∈E , specified vertices s, t ∈V , positive integer B≤ | V | and positive integer K , is there a partition of V into dist sets V1 and V2 such that s ∈ V1 ,t∈V2 ,| V1 | ≤ B ,| V2 | ≤ B , and such that the sum of the weights of the edges from the E that have one endpoint in V1 and one endpoint in V2 is no more than K ? [GJ79] minimum cut linear arrangement INSTANCE: Graph G = (V, E) . SOLUTION: A one-to-one function f : V → [1, 2, … , | V | ] . MEASURE: Maximum number of cut edges in any integer point max i ∈ [ 1 … | V | ] |{(u, v) ∈ E : f(u) ≤ i
integer B . SOLUTION: A spanning subgraph E ' ⊆ E for G such that the sum of the weights of the edges in E' does not exceed B . MEASURE: The diameter of the spanning subgraph. [CK00] minimum diameters decomposition INSTANCE: Graph G = (V, E) . SOLUTION: A decomposition of the graph into two factors, F1 and F2 , with equal diameters. MEASURE: The diameter of F1 . [CK00] minimum directed bandwidth INSTANCE: Directed acyclic graph G = (V, A) . SOLUTION: A linear ordering of V , i.e. a one-to-one function f : V→ {1, 2, … , | V |} such that, for all (u, v) ∈A , f(u) < f(v) . MEASURE: The bandwidth of the ordering max (u, v) ∈ A f(u) – f(v) . [CK00] minimum dominating set INSTANCE: Graph G = (V, E) . SOLUTION: A dominating set for G , i.e., a subset V'⊆V such that for all u∈V – V'there is a v ∈V' for which (u, v) ∈E . MEASURE: Cardinality of the dominating set | V' | . [CK00] minimum edge coloring INSTANCE: Graph G = (V, E) . SOLUTION: A coloring of E , i.e., a partition of E into dist sets E1 , E2 , … , Ek such that, for 1 ≤ i ≤ k , no two edges in Ei share a common endpoint in G . MEASURE: Cardinality of the coloring, i.e., the number of dist sets Ei . [CK00] minimum edge-cost flow problem Given a digraph G = (V, A) , specified vertices s and t , capacity c(a) ∈Z+ and price p(a) ∈Z0+for each a ∈ A , requirement R∈Z+and a bound B ∈Z+ , is there a flow function f : A →Z0+ such that  f(a) ≤ c(a) for all a ∈ A ,  for each v ∈ V – {s, t} , Σ (u, v) ∈A f((u, v)) = Σ (v, u)∈ A f((v, u)) ,  Σ (u, t) ∈ A f((u, t)) - Σ (t, u) ∈ A f((t, u)) ≥ R ,  if A ' = {a ∈ A : f(a) ≠ 0} , then Σ a ∈ A ' p(a) ≤ B ? [GJ79] minimum edge deletion k-partition INSTANCE: Graph G = (V, E) and a weight function w : E → N .

SOLUTION: A k-partition, i.e., a color assignment c : V → [1 … k] . MEASURE: The weight of the monochromatic edges Σ

(v1, v2) ∈ E : c(v1) = c(v2)

w(v1, v2) . [CK00]

minimum edge deletion to obtain subgraph with property P INSTANCE: Directed or undirected graph G = (V, E) . SOLUTION: A subset E' ⊆ E such that the subgraph G' = (V, E' – E) has the property P . MEASURE: Cardinality of the set of deleted edges | E' | . [CK00] minimum edge dominating set INSTANCE: Graph G = (V, E) . SOLUTION: An dominating edge set for G , i.e., a subset E'⊆E such that for all e1∈E – E' there is an e2 ∈E' such that e1 and e2 are adjacent. MEASURE: Cardinality of the dominating edge set | E' | . [CK00] minimum edge k-spanner INSTANCE: Connected graph G = (V, E) . SOLUTION: A k-spanner of G , i.e., a spanning subgraph G' of G such that, for any pair of vertices u and v , the length of the shortest path between u and v in G' is at most k times the distance between u and v in G . MEASURE: The number of edges in G' . [CK00] minimum equivalent digraph INSTANCE: Directed graph G = (V, A) . SOLUTION: A subset A' ⊆ A such that, for every ordered pair of vertices u, v ∈V , the graph G' = (V, A' ) contains a directed path from u to v if and only if G does. MEASURE: Cardinality | A' | . [CK00] minimum equivalent digraph problem Given a digraph G = (V, A) and positive integer K ≤ | A | , is there a subset A ' ⊆ Awith | A ' | ≥ Ksuch that for every ordered pair of vertices u, v ∈V , the graph G ' = (V, A ' ) contains a directed path from u to v if and only if G does? [GJ79] minimum arc set INSTANCE: Directed graph G = (V, A) . SOLUTION: A arc set, i.e., a subset A' ⊆ A such that A' contains at least one arc from every directed cycle in G . MEASURE: Cardinality of the arc set | A' | .[CK00] minimum vertex set INSTANCE: Directed graph G = (V, A) . SOLUTION: A vertex set, i.e., a subset V' ⊆ V such that V' contains at least one vertex from every directed cycle in G . MEASURE: Cardinality of the vertex set

| V' | . [CK00] minimum file transfer scheduling INSTANCE: A file transfer graph, i.e., a graph G = (V, E) , a port constraint function p : V → N and a file length function L : E →N . SOLUTION: A file transfer schedule, i.e., a function S : E→N such that, for each vertex v and for each t ∈N , |{u : (u, v) ∈E ≤ s(e) ≤ t ≤ s(e) + L(e)}| ≤ p(v) . MEASURE: The makespan of the schedule max e ∈ E ( s(e) + L(e) ) . [CK00] minimum flow A legal flow for which the total flow is minimum. [SE79] minimum general routing INSTANCE: Graph G = (V, E) , length l(e) ∈N for each e ∈E , subset E'⊆E , subset V' ⊆V . SOLUTION: A cycle in G that visits each vertex in V' exactly once and traverses each edge in E' . MEASURE: The total length of the cycle. [CK00] minimum generalized Steiner network INSTANCE: Graph G = (V, E) , a weight function w : E → N , a capacity function c : E →N , and a requirement function r : V× V→N . SOLUTION: A Steiner network over G that satisfies all the requirements and obeys all the capacities, i.e., a function f : E→N such that, for each edge e , f(e) ≤ c(e) and, for any pair of nodes i and j , the number of edge dist paths between i and j is at least r(i, j) where, for each edge e , f(e) copies of e are available. MEASURE: The cost of the network Σ e ∈ Ew(u) f(e) . [CK00] minimum geometric 3-degree spanning tree INSTANCE: Set P ⊆ Z × Z of points in the plane. SOLUTION: A spanning tree T for P in which no vertex has degree larger than 3. MEASURE: The total weight of the spanning tree, i.e., Σ (u, v) ∈ T d(u, v) , where d(u, v) is the Euclidean distance between u and v . [CK00] minimum geometric Steiner tree INSTANCE: Set P ⊆ Z × Z of points in the plane. SOLUTION: A finite set of Steiner points Q ⊆Z× Z . MEASURE: The total weight of the minimum spanning tree for the vertex set P∪Q , where the weight of an edge ⟨ (x1, y1), (x2, y2) ⟩ is the discretized Euclidean length  [ (x1 – x2 )2 + (y1 – y2 )2 ]1/2  . [CK00] minimum graph coloring INSTANCE: Graph G = (V, E) .

SOLUTION: A coloring of G , i.e., a partition of V into dist sets V1 , V2 , … , Vk such that each Vi is an independent set for G . MEASURE: Cardinality of the coloring, i.e., the number of dist independent sets Vi . [CK00] minimum graph inference INSTANCE: Class C of undirected edgecolored graphs, string x of colors. SOLUTION: A graph G ∈ | C | and a simple path in G such that the string of colors traversed in the path is equal to x . MEASURE: Cardinality of the edge set of G . [CK00] minimum graph motion planning INSTANCE: Graph G = (V, E) , start vertex s∈V where the robot is initially placed, goal vertex t ∈V , and a subset W ⊆ V of vertices where the obstacles are initially placed. SOLUTION: A motion scheme for the robot and the obstacles. In each time step either the robot or one obstacle may be moved to a neighbouring vertex that is not occupied by the robot or an obstacle. MEASURE: The number of steps until the robot has been moved to the goal vertex t . [CK00] minimum graph transformation INSTANCE: Graphs G1 = (V1, E1) and G2 = (V2, E2) . SOLUTION: A transformation that makes G1 isomorphic to G2 . In the transformation a set of edges E' ⊆E1 is removed from E1 and added to E2 . MEASURE: Cardinality of the transformation set | E ' | . [CK00] minimum independent dominating set INSTANCE: Graph G = (V, E) . SOLUTION: An independent dominating set for G , i.e., a subset V'⊆V such that for all u ∈V – V' there is a v ∈V' for which (u, v) ∈E , and such that no two vertices in V' are ed by an edge in E . MEASURE: Cardinality of the independent dominating set | V' | . [CK00] minimum interval graph completion INSTANCE: Graph G = (V, E) . SOLUTION: An interval graph G' = (V, E' ) that contains G as a subgraph, i.e. E ⊆E' . An interval graph is a graph whose vertices can be mapped to distinct intervals in the real line such that two vertices in the graph have an edge between them if and only if their corresponding intervals overlap. MEASURE: The cardinality of the interval graph | E' | . [CK00] minimum k-capacitated tree partition INSTANCE: Graph G = (V, E) , and a weight function w : E → N . SOLUTION: A k-capacitated tree partition of G , i.e., a collection of vertex dist subsets

E1 , E2 , … , Em of E such that, for each i , the subgraph induced by Ei is a tree of at least k vertices. MEASURE: The weight of the partition Σ i Σ e ∈ Ei w(e) . [CK00] minimum k-center INSTANCE: Complete graph G = (V, E) and distances d( vi , vj ) ∈N satisfying the triangle inequality. SOLUTION: A k-center set, i.e., a subset C ⊆V with | C | = k . MEASURE: The maximum distance from a vertex to its nearest center max v∈ V min c∈ C d( v, c) . [CK00] minimum k-Chinese postman problem INSTANCE: Multigraph G = (V, E) , initial vertex s ∈ V , length l(e) ∈N for each e ∈E . SOLUTION: A collection of k cycles, each containing the initial vertex s , that collectively traverse every edge in the graph at least once. MEASURE: The maximum length of the k cycles. [CK00] minimum k-connected subgraph problem Given a graph G = (V, E) , positive integers K ≤ | V | and B ≤ | E | , is there a subset E ' ⊆Ewith | E ' | ≥ B such G ' = (V, E ' ) is k-connected? [GJ79] minimum k-cut INSTANCE: Graph G = (V, E) , a weight function w : E → N , and an integer k ∈ [ 2 … | V | ] . SOLUTION: A partition of V into k dist sets F = { C1 , C2 , … , Ck } . MEASURE: The sum of the weight of the edges between the dist sets Σ 1 k-1 Σ i+1 kΣ v1 ∈C i , v2 ∈C jw({v1, v2}) . [CK00] minimum k-edge connected subgraph INSTANCE: Graph G = (V, E) , k is a constant, k≥ 2. SOLUTION: A k-edge connected spanning subgraph G' = (V, E' ) for G , i.e. a spanning subgraph that cannot be disconnected by removing fewer than k edges. MEASURE: The cardinality of the spanning subgraph | E' | .[CK00] minimum k-median INSTANCE: Complete graph G = (V, E) and distances d(e) ∈N . SOLUTION: A k-median set, i.e., a subset V' ⊆V with | V' | = k . MEASURE: The sum of the distances from each vertex to its nearest median Σ v, w) . [CK00] minimum k-spanning tree

v∈V

min w∈ V ' d(

INSTANCE: Graph G = (V, E) , an integer k≤ n , and a weight function w : E →N . SOLUTION: A k-spanning tree, i.e., a subtree T of G of at least k nodes. MEASURE: The weight of the tree Σ e ∈ T w(e) . [CK00] minimum k-stacker-crane problem INSTANCE: Mixed graph G = (V, A, E) , initial vertex s ∈ V , length l(e) ∈N for each e ∈A∪E . SOLUTION: A collection of k cycles, each containing the initial vertex s , that collectively traverse each directed edge in A at least once. MEASURE: The maximum length of the k cycles. [CK00] minimum k-supplier INSTANCE: Complete graph G = (V, E) , distances d(vi , vj) ∈N satisfying the triangle inequality, center construction cost c(v) ∈N and usage weight w(v) for each v ∈ V , cost bound L∈N . SOLUTION: A supplier set of legal cost, i.e., a subset S ⊆V such that Σ v ∈ S c(v) ≤ L . MEASURE: The maximum weighted distance from a vertex to its nearest supplier max v∈ V min s∈ S w(e) d( v, s ) . [CK00] minimum k-switching network INSTANCE: Complete graph G = (V, E) and distances d(vi , vj) ∈N satisfying the triangle inequality. SOLUTION: A partition F = {A1 , A2 , … , Ak , B1 , B2 , … , Bk} of V . MEASURE: Maximum distance between vertices in different sets with the same index max i ∈ [1…k] max v1 ∈ Ai , v2 ∈ Bid(v1 , v2) . [CK00] minimum k-vertex connected subgraph INSTANCE: Graph G = (V, E) , k is a constant, k≥ 2. SOLUTION: A k-vertex connected spanning subgraph G' = (V, E' ) for G , i.e. a spanning subgraph that cannot be disconnected by removing fewer than k vertices. MEASURE: The cardinality of the spanning subgraph | E' | .[CK00] minimum linear arrangement INSTANCE: Graph G = (V, E) . SOLUTION: A one-to-one function f : V → [1, 2, … , | V| ] . MEASURE: The total length of the edges in the linear arrangement max (u, v) ∈ E | f(u) – f(v) | . [CK00] minimum maximal matching INSTANCE: Graph G = (V, E) . SOLUTION: A maximal matchingE' , i.e., a subset E'⊆E such that no two edges in E' shares a common endpoint and every edge in E – E' shares a common endpoint with some edge in E' .

MEASURE: Cardinality of the matching | E' | . [CK00] minimum maximal matching problem Given a graph G = (V, E) and positive integer K ≤ | E | , is there a subset E ' ⊆ Ewith | E ' | ≤ K such that E ' is a maximal matching? [GJ79] minimum maximum dist connecting paths INSTANCE: Graph G = (V, E) , length function l : E → N , and a pair of vertices s , t in V . SOLUTION: Two vertex dist paths in G connecting s and t , i.e. two sequences of vertices u1 , u2 , … , um and v1 , v2 , … , vm such that |{ u1 , u2 , … , um , v1 , v2 , … , vm }| = m + n , (s , u1) , (s, v1) , (um , t) , and (vn , t) are included in E , and for any i , (ui , ui+1) and (vi , vi+1) are included in E . MEASURE: The longest of the two paths, i.e. max [l(s, u) + Σ i=1 m-1l(ui , ui+1) + l(um , t) + + Σ i=1 n-1l(vi , vi+1) + l(vn , t)] .[CK00] minimum metric bottleneck wandering salesperson problem INSTANCE: Set C of m cities, an initial city s∈C , a final city f∈ C , distances d( ci , cj ) ∈N satisfying the triangle inequality. SOLUTION: A simple path from the initial city s to the final city f ing through all cities in C , i.e., a permutation π : [ 1 … m ] → [ 1 … m ] such that vπ (i) = s and vπ (m) = f . MEASURE: The length of the largest distance in the path max i ∈ [ 1 … m-1 ] d({ cπ (i) , cπ (i+1)}) . [CK00] minimum metric dimension INSTANCE: Graph G = (V, E) . SOLUTION: A metric basis for G , i.e., a subset V ' ⊆ V such that for each pair u, v ∈V there is a w ∈ V ' such that the length of the shortest path from u to w is different from the length of the shortest path from v to w . MEASURE: The cardinality of the metric basis | V ' | .[CK00] minimum metric traveling k-salesperson problem INSTANCE: Set C of m cities, an initial city s∈C , distances d( ci , cj ) ∈N satisfying the triangle inequality. SOLUTION: A collection of k subtours, each containing the initial city s , such that each city is in at least one subtour. MEASURE: The maximum length of the k subtours. [CK00] minimum metric traveling salesperson INSTANCE: Set C ⊆ Z × Z of m points in the plane.

SOLUTION: A tour of C i.e., a permutation π : [ 1 … m ] →[ 1 … m ] . MEASURE: The length of the tour, where the distance between (x1 , y1) and (x2 , y2) is the discretized Euclidean length  [(x1 – x2) 2 + (x1 – x2) 2 ] ½ . [CK00] minimum metric traveling salesperson problem INSTANCE: Set C of m cities, distances d( ci , cj ) ∈N satisfying the triangle inequality. SOLUTION: A tour of C , i.e., a permutation π : [ 1 … m ] →[ 1 … m ] . MEASURE: The length of the tour. [CK00] minimum multicut INSTANCE: A graph G = (V, E) , a set S⊆V× V of source-terminal pairs, and a weight function w : E →N . SOLUTION: A multi-cut, i.e., a set E' ⊆E such that the removal of E' from E disconnects si from ti for every pair ( si , ti ) ∈S . MEASURE: The weight of the cut Σ e ∈ E ' w(e) . [CK00] minimum multiway cut INSTANCE: A graph G = (V, E) , a set S⊆Vof terminals, and a weight function w : E → N . SOLUTION: A multiway cut, i.e., a set E' ⊆E such that the removal of E' from E disconnects each terminal from all the others. MEASURE: The weight of the cut Σ e ∈ E ' w(e) . [CK00] minimum network inhibition on planar graphs INSTANCE: Planar graph G = (V, E) , capacity function c : E → N , destruction cost function d : E → N , and budget B . SOLUTION: An attack strategy to the network, i.e., a function α : E → [ 0, 1 ] such that Σ e ∈ Eα (e) d(e) ≤ B . MEASURE: The capability left in the damaged network, i.e., the minimum cut in G with capacity c' defined as c' (e) = α (e) c(e) . [CK00] minimum numerical taxonomy INSTANCE: n × n distance matrix D . SOLUTION: Tree metric dT , i.e., an edge weighted tree T of n nodes such that dT (i, j) is the distance between i and j in T . MEASURE: max i<j | dT (i, j) – D[i, j] | . [CK00] minimum phylogenetic tree distance INSTANCE: A 3-degree (binary) tree T = (V, E) with unique labels on the leaves and with edge weights w : E→N . A 3-degree tree T' with the same set of unique labels as T . SOLUTION: A sequence of edges e1 , … , emrepresenting nearest neighbour interchanges

transforming the tree T into T' (so that the labels match). A nearest neighbour interchange of ei = {u, v} is a transformation where one of the two subtrees adjacent to u is exchanged with one of the two subtrees adjacent to v . MEASURE: The cost of the sequence of interchanges Σ 1 ≤ i ≤ m w(ei) .[CK00] minimum P-object For a property P, no smaller object of the same type also has property P. [DW96] minimum point-to-point connection INSTANCE: Graph G = (V, E) , a weight function w : E → N , a set of sources S = {s1, … , sp} , and a set of destinations D = {d1, … , dp} . SOLUTION: A point-to-point connection, i.e., a subset E' ⊆E such that each source-destination pair is connected in E' . MEASURE: The weight of the connection Σ e ∈ E ' w(e) . [CK00] minimum precedence constrained sequencing with delays INSTANCE: Set T of tasks, a directed acyclic graph G = (T, E) defining precedence constraints for the tasks, a positive integer D , and for each task an integer delay 0 ≤ d(t) ≤ D . SOLUTION: A one-processor schedule for T that obeys the precedence constraints and the delays, i.e., an injective function S : T→Z+ such that, for each edge < ti , tj > ∈E , S(tj) – S(ti) > d(ti) . MEASURE: The finish time for the schedule max t ∈ T s(t) . [CK00] minimum quotient cut INSTANCE: Graph G = (V, E) , a vertex-weight function w : E → N , and an edge-cost function c : E →N . SOLUTION: A cut C , i.e., a subset C ⊆V . MEASURE: The quotient of the cut, i.e., c(C) / min {w(C), w(V – C)} where c(C) denotes the sum of the costs of the edges (u, v) such that either u∈C and v∉C or u∉C and v∈Cand, for any subset V ' ⊆V ,w(V ' ) denotes the sum of the weights of the vertices in V ' . [CK00] minimum ratio cut INSTANCE: Graph G = (V, E) , a capacity function c : E → N , and k commodities, i.e., k pairs ( si , ti ) ∈V 2 and a demand di for each pair. SOLUTION: A cut, i.e., a partition of V into two dist sets V1 and V2 . MEASURE: The capacity of the cut divided by the demand across the cut Σ v1 ∈ V1 , v2 ∈ V2 , (v1, v2) ∈ E [c(vi1, v2)] / Σ i : | {si, ti} ∩ V1 | = 1 [di ] . [CK00] minimum rectilinear global routing

INSTANCE: m × n-array of gates, collection C of nets, i.e., 3-sets of gates. SOLUTION: Wires following rectilinear paths connecting the gates in each net. MEASURE: The largest number of wires in the same channel between two gates in the array. [CK00] minimum sufficiency INSTANCE: Directed acyclic graph G = (V, E) . SOLUTION: Computation for G that uses k s, i.e., an ordering v1 , … , vn of the vertices in V and a sequence S0 , … , Sn of subsets of V , each satisfying | Sn | ≤ k , such that S0 is empty, Sn contains all vertices with in-degree 0 in G , and, for 0 ≤ i ≤ n , vi ∈Si , Si – { vi } ⊆Si-1 and Si-1 contains all vertices u for which (vi , u) ∈A . MEASURE: Number of s k . [CK00] minimum routing tree congestion INSTANCE: Graph G = (V, E) and a weight function w : E → N . SOLUTION: A routing tree T for G , i.e., a tree T in which each internal vertex has degree 3 and the leaves correspond to vertices of G . MEASURE: The congestion of the routing tree, i.e., the maximum, for any edge e , of Σ (u, v) ∈ E , u ∈ S, v ∉ Sw(u, v) . [CK00] minimum schedule length INSTANCE: A network N = (V, E, b, c) where G = (V, E) is a graph, b : V →N is the vertex-capacity function, and c : E →N is the edge-capacity function, and a set T of tokens t = (u, v, p) where u, v∈Vand p is either a path from u to v or the empty set. SOLUTION: A schedule S , i.e., a sequence f0 , … , fl of configuration functions fi : T → V such that  for any token t = (u, v, p) , f0 (t) = u and , fl (t) = v ;  for any 0 ≤ i ≤ l – 1 and for any token t , if fi (t) = v and fi+1 (t) = w then (a) (u, v) ∈ E , (b) | t' : fi (t' ) = w }| < b(w) , (c) | t' : fi+1 (t' ) = w }| ≤ b(w) , and (d) | t' : fi (t' ) = v ≤ fi+1 (t' ) = w}| ≤ c(v, w) . MEASURE: The length of the schedule, i.e., l . [CK00] minimum single-sink edge installation INSTANCE: Graph G = (V, E) , length function l : E → N , set of sources S ⊆ V , sink t ∈ V , demand function d : S →Z+ , finite set of cable types where each cable type is specified by its capacity and its cost per unit length. SOLUTION: A network of cables in the graph, consisting of an integral number of each cable type for each edge in G , that routes all the demands at the sources to the sink. The demand of each source must follow a single path from source to sink. MEASURE: The total cost of building the network of cables. [CK00]

minimum size ultrametric tree INSTANCE: n × n matrix M of positive integers. SOLUTION: An ultrametric tree, i.e., an edge-weighted tree T(V, E) with n leaves such that, for any pair of leaves i and j , dijT≥ M [i, j] where dijT denotes the sum of the weights in the path between i and j . MEASURE: The size of the tree, i.e., Σ e ∈ E w(e) where w(e) denotes the weight of edge e . [CK00] minimum spanning tree = MST The minimum spanning tree of a weighted graph is a set of n – 1 edges of minimum total weight which form a spanning tree of the graph. [EW00] A minimum-weight tree in a weighted graph which contains all of the graph's vertices. [PEB00] minimum stacker crane problem INSTANCE: Mixed graph G = (V, A, E) , length l(e) ∈ N for each e∈A∪E such that for every arc there is a parallel edge of no greater length. SOLUTION: A cycle in G (possibly containing repeated vertices) that includes each directed edge in A at least once, traversing such edges only in the specified direction. MEASURE: The total length of the cycle. [CK00] minimum Steiner tree INSTANCE: Complete graph G = (V, E) , a metric given by edge weights s : E →N and a subset S ⊆V of required vertices. SOLUTION: A Steiner tree, i.e., a subtree of G that includes all the vertices in S . MEASURE: The sum of the weights of the edges in the subtree. [CK00] minimum storage time sequencing INSTANCE: Set T of tasks, a directed acyclic graph G = (T, E) defining precedence constraints for the tasks, for each task a length l(t) ∈Z+ , and for each edge in the graph a weight w(t1 , t2) measuring the storage required to save the intermediate results generated by task t1 until it is consumed by task t2 . SOLUTION: A one-processor schedule for T that obeys the precedence constraints, i.e., a permutation π : [1 … | T | ] → [1 … | T | ] such that, for each edge < ti , tj > ∈E ,π -1 (i) < π -1 (j) . MEASURE: The total storage-time product Σ < tw(i) , tw(j) > ∈ E w(tπ (i) , tπ (i) ) Σ k=min(i, j)max(i, j)l(tπ (i) ) .[CK00] minimum strong connectivity augmentation INSTANCE: Directed graph G = (V, A) and a weight function w : V × V → N . SOLUTION: A connectivity augmenting set A' for G , i.e., a set A' of ordered pairs of vertices from V such that G' = (V, A ∪ A' ) is strongly connected. MEASURE: The weight of the augmenting set Σ (u, v) ∈ E ' w(u, v) . [CK00]

minimum time-cost tradeoff INSTANCE: Set J of activities, a directed acyclic graph G = (T, E) defining precedence constraints for the activities, a positive budget B , and for each activity j ∈J a non-increasing cost function cj described as a step function with lj steps: cj (t) =  if 0 ≤ t < aj,1 ; cj (t) = cj (aj, i ) if aj, i ≤ t < aj, i+1 , 1 ≤ i < lj ; cj (t) = 0 if aj, lj ≤ t ; where α > cj (aj, 1 ) > … > cj (aj, lj ) . SOLUTION: A one-processor schedule for J that obeys the precedence constraints and activities durations tj > 0 for each j∈J that obeys the budget Σ j ∈ Jcj (tj ) ≤ B . MEASURE: The total duration of all activities Σ j ∈ Jtj . [CK00] minimum traveling repairman INSTANCE: Graph G = (V, E) , start vertex r∈V , length l(e) ∈Nfor each e∈E satisfying the triangle inequality. SOLUTION: A walk starting in r visiting all vertices in G , i.e., a permutation π : [ 1 … m ] such that π (i) = r , where π describes in which order the vertices are visited for the first time. MEASURE: Σ v∈ V dπ (r, v) , where dπ (r, v) is the total distance traversed in the walk from r until we first visit v . [CK00] minimum traveling salesperson INSTANCE: Set C of m cities, distances d( ci , cj ) ∈Nfor each pair of cities c1 , cj ∈C . SOLUTION: A tour of C , i.e., a permutation π : [ 1 … m ] →[ 1 … m ] . MEASURE: The length of the tour d({ cπ (m) , cπ (1)}) + Σ π (i)m-1d({ cπ (i) , cπ (i+1)}) . [CK00] minimum tree alignment INSTANCE: Set S of sequences over an alphabet Σ , a score scheme µ : Σ ∪ {∆ } × Σ ∪ {∆ } → N satisfying the triangle inequality, and a tree T of bounded degree whose leafs are labeled with the sequences S . SOLUTION: A sequence labeling of the interior nodes of the tree T . MEASURE: The total alignment cost of the labeled tree, i.e., the sum over all edges (x, y) in the tree of the edit distance d(x, y) between the labels of the endpoints of the edge. The edit distance is the minimum alignment cost Σ iµ (x' [ i ] , y' [ i ]) over all possible alignments x' and y' of x and y . An alignment is obtained by inserting spaces (denoted by ∆ ) into the original sequence, either between two characters or in the beginning or at the end. Alignments x' and y' must have the same length. [CK00] minimum tree compact packing INSTANCE: A tree T = (V, E) , a node-weight function w : V → Q+ such that Σ and a page-capacity p .

w(v) = 1 ,

v∈V

SOLUTION: A compact packing of T into pages of capacity p , i.e., a function τ : V →Z+ such that | τ -1 (i) | = p . MEASURE: The number of page faults of the packing, i.e., Σ v ∈ V cτ (v) w(v) where cτ (v) = Σ i=0 l(v)-1∆ τ (vi) , l(v) denotes the number of edges in the path from the root to v , vi denotes the ith node in this path, and ∆ τ (v) is equal to 0 if the parent of v is assigned the same page of u , and it is equal to 1 otherwise.[CK00] minimum tree width INSTANCE: Graph G = (V, E) . SOLUTION: A tree decomposition, i.e., a pair ({Xi : i ∈ I}, T) where T = (I, F) is a tree and Xi is a collection of subsets of V , such that  ∪ i∈ IXi = V ,  for any (v, w) ∈ E , there exists an i ∈ I with u, v ∈ Xi ,  for any v ∈ V , the set { i∈I : v ∈Xi } forms a connected subtree of T . MEASURE: The tree width of the tree decomposition max i ∈ I | Xi | – 1 . [CK00] minimum unsplittable flow INSTANCE: Graph G = (V, E) , with edge capacities c : E → Z+ , source vertex s , collection of sinks t1 , … , tk with associated non-negative integer demands ρ 1 , … , ρ k such that, ρ i≤ c(e) for all e∈E and i∈ [1 … k] . SOLUTION: A single s-ti flow path for each commodity i so that the demands are satisfied and the total flow routed across any edge e is bounded by c(e) . MEASURE: max e ∈ E f(e) / c(e) where f(e) is the total flow routed across e . [CK00] minimum upgrading spanning tree INSTANCE: Graph G = (V, E) , three edge weight functions d2(e) ≤ d1(e) ≤ d0(e) (for each e∈E ), where di(e) denotes the weight of edge e if i of its endpoints are "upgraded", vertex upgrade costs c(v) (for each v ∈V ), a threshold value D for the weight of a minimum spanning tree. SOLUTION: An upgrading set W ⊆V of vertices such that the weight of a minimum spanning tree in G with respect to edge weights given by dW is bounded by D . Here, dW denotes the edge weight function resulting from the upgrade of the vertices in W , i.e., dW (u, v) = di (u, v) , where | W∩ {u, v} | = i . MEASURE: The cost of the upgrading set c(W) = Σ v ∈ W c(v) . [CK00] minimum vehicle scheduling on tree INSTANCE: Rooted tree T = (V, E, w0) , a forward travel time f : E →N, a backward travel time b : E →N , a release time τ : E →N , and an handling time h : E →N . SOLUTION: A vehicle routing schedule that starts from v0 , visits all nodes of T , returns to v0 , and, for any node vi , starts processing vi not before the release time r(vi) , i.e., a permutation π of 1 , … , | V | and a waiting function w such that, for any i , d(v0 , vπ (1) ) + Σ j=1 i-1 [w(vπ (j)) +

h(vπ (j)) + d(vπ (j) , vπ (j+1))] ≥ r(vπ (j) ), where d(u, v) denotes the length of the unique path from u to v . MEASURE: The total completion time d(v0 , vπ (1) ) + Σ j=1 i-1 [ w(vπ ( j )) + h(vπ ( j )) + d(vπ ( j ) , vπ (j+1))] + w(vπ (n)) + h(vπ (n)) + d(vπ ( n) , v0) .[CK00] minimum vertex cover INSTANCE: Graph G = (V, E) . SOLUTION: A vertex cover for G , i.e., a subset V' ⊆ V such that, for each edge (u, v) ∈ E , at least one of u and v belongs to V' . MEASURE: Cardinality of the vertex cover | V' | . [CK00] minimum vertex cut The smallest set of vertices in an undirected graph which separate two distinct vertices. That is, every path between them es through some member of the cut. [PEB00] minimum vertex deletion to obtain subgraph with property P INSTANCE: Directed or undirected graph G = (V, E) . SOLUTION: A subset V' ⊆ V such that the subgraph induced by V – V'has the property P . MEASURE: Cardinality of the set of deleted vertices | V' | .[CK00] minimum vertex dist cycle cover INSTANCE: Graph G = (V, E) . SOLUTION: A family F of vertex dist cycles covering V . MEASURE: Number of cycles in F . [CK00] minimum vertex k-cut INSTANCE: Graph G = (V, E) , a set S = { s1 , t1 , … , sk , tk }of special vertices, a weight function w : V – S → N , and an integer k . SOLUTION: A vertex k-cut, i.e., a subset C ⊆ V – S of vertices such that their deletion from G disconnects each si from ti for 1 ≤ i ≤ k . MEASURE: The sum of the weight of the vertices in the cut Σ v ∈ C w(v) . [CK00] minimum weight and/or graph solution problem Given acyclic digraph G = (V, A) with a single vertex s∈V having in-degree 0, assignment f(v) ∈ {and, or} for each v ∈ V having nonzero out-degree, weight w(a) ∈Z+for each a∈A and a positive integer K , is there a subgraph G ' = (V ', A ' ) of G such that s ∈ V ' , such that if v ∈ V ' and f(v) = and then all arcs leaving v in A belong to A ' , such that that if v ∈ V ' and f(v) = or then at least one of the arcs leaving v in A belongs to A ' , and such that the sum of the weights of the arcs in A ' does not exceed K ? [GJ79] min-max multicenter problem

Given a graph G = (V, E) , weight w(v) ∈Z0+for each v ∈V , length l(e) ∈Z0+for each e ∈ E , positive integer K≤ | V | and positive rational number B , is there a set P of K points on G (where a point on G can be either a vertex in V or a point on edge e ∈ Ewith e regarded as a line segment of length l(e) ) such that if d(v) is the length of the shortest path from v to the closest point in P , then max { d(v) • w(v) : v ∈ V } ≤ B ? [GJ79] minor = subcontraction Graph or matroid obtained by a sequence of deletions and contractions. [DW96] minor graph A sort of subgraph which Kuratowski means when he says "contain". It is roughly a small graph which can be mapped into the big one without merging vertices. [EW00] minor of a graph A graph F is a minor of a graph G if F can be obtained from a subgraph of G by a sequence of deletions and contractions of edges. [BW97] min-sum multicenter problem Given a graph G = (V, E) , weight w(v) ∈Z0+for each v ∈V , length l(e) ∈Z0+for each e ∈ E , positive integer K≤ | V | and positive rational number B , is there a set P of K points on G such that if d(v) is the length of the shortest path from v to the closest point in P , then Σ v∈ Vd(v) •w(v) ≤ B ? [GJ79] mixed graph A graph that contains both directed and undirected edges. [HC00] A graph that contains both directed and undirected edges. FIGURE

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh |

mj-mz

mi | | | n | o | p | q | r | s-so | sp-sz | t | u | v | w | xyz | | modular | multigraph | mutual | Möbius climber The Möbius climber was designed by Gerald Harnett, a mathematics professor at Florida Atlantic University in Boca Raton, with the assistance of Jerome Schwartz and Sean Powers. It consists of 64 triangles linked together and mounted so that, at any one point, the twisted structure appears to have four sides, but overall turns out to have just two. [IP00] FIGURE

Möbius ladder The graph obtained by adding to an even cycle the chords between vertex pairs at maximum distance on the cycle (can be drawn as a ladder with a twist). [DW96] The Mobius ladder of order 2n , M n , is the 3-regular graph with a Hamiltonian cycle (1, 2, ..., 2n, 1) and edges ing vertex i to i + n , i = 1, ... , n .[DA00] Möbius strip The nonorientable surface obtained by identifying two opposite sides of a rectangle using opposite orientation. [DW96] FIGURE

model A Probability distribution making the graphs with vertex set [n] equally likely. [DW96] model B Probability distribution making the graphs with vertex set [n] and m edges equally likely. [DW96] modular function Let S be a finite set. Let f : 2S →R , f is said to be a modular function if f(X) + f(Y) = f(X ∪ Y) + f(X ∩ Y)∀X , Y⊆S.[HN97] monochromatic In a coloring, a set having all elements the same color. [DW96] monochromatic triangle problem Given a graph G = (V, E) , is there a partition of E into two dist sets E1 , E2 such that neither G1 = (V , E1) nor G2 = (V , E2) contains a triangle? [GJ79] monotone graph property Preserved under deletion of edges or vertices. [DW96] Moore graph (r, g)-cage of order f0 (r, g) .[CL96] FIGURE

more for less paradox This was originally introduced in the context of linear network flows: It is possible to send more flow from supply to demand nodes at lower cost, even if all arc costs are positive. [HG99] Morishima matrix Square matrix A for which there is a set S so that aij ≥ 0 if i and j are both in S or both not in S and aij ≤ 0 otherwise. [TZ98]

MST = minimum spanning tree M-tree A tree not having the complete bipartite graph K1, 2 with base at the vertex of degree two as a limb. [EW00] multi suffix tree A suffix tree extended to multiple strings by concatenating the strings. [PEB00] multi-commodity flow problem A network flow problem in which more than one commodity share arc capacities. This applies to communication networks as well as to shipments of different grains on barges of limited capacities. It is more complicated than the single-commodity flow, generally NP-complete (except for some special cases). [HG99] multidigraph A digraph with more than one arc in the same direction to two vertices. [CL96] multigraph = nonsimple graph A graph with multiple edges allowed. [BW97] Informally, a multigraph is a graph with multiple edges between the same vertices. Formally: a multigraph is a set V of vertices along, a set E of edges, and a function f from E to {{u,v} | u,v in V; u, v distinct}. (The function f shows which vertices are connected by which edge.) The edges r and s are called parallel or multiple edges if f(r) = f(s) .[CC99] FIGURE

multiple choice branching problem Given a digraph G = (V, A) , weight w(a) ∈Z0+for each a ∈A , a partition of A into dist sets A1 , A2 , … , Am and a positive integer K , is there a subset A ' ∈Awith Σ a ∈ A ' w(a) ≤ K such that no two arcs in A ' enter the same vertex, A ' contains no cycles and A ' contains at most one arc from each of the Ai , 1 ≤ i ≤ m ? [GJ79] multiple choice matching problem Given digraph G = (V, E) , partition of E into dist sets E1 , E2 , … , EJ and positive integer K , is there a subset E1' ⊆E1with | E' | ≥ K such that no two edges in E ' share a common vertex and such that E' contains at most one edge from each Ei , 1 ≤ i≤ J ? [GJ79] multiple copy file allocation problem Given a graph G = (V, E) , for each v∈Va usage u(v) ∈ Z+and a storage cost s(v) ∈Z+ , and a positive integer K , is there a subset V ' ⊆V such that, if for each v∈Vwe let d(v) denote the number of edges in the shortest path in G from v to a member of V ' , we have Σ v∈ V ' s(v) + Σ v∈ Vd(v) •u(v) ≤ K ?[GJ79] multiple edges Two or more edges ing the same pair of vertices. [BW97]

Two or more edges with the same endpoints and the same sign or gain. (Whether to count a negative loop and a half edge at the same vertex as multiple edges is not clear and may depend on the context.) [TZ98] A pair (a, b) contained two or more times in the edge set S . FIGURE

multiple interval representation Intersection representation with a union of intervals for each vertex. [DW96] multiway tree A tree with any number of children for each node. [PEB00] FIGURE

M-unsaturated Vertex not belonging to an edge of M . [DW96] mutual reachability An equivalence relation on vertices of a digraph. [DW96]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |

n | o | p | q | r | s-so | sp-sz | t | u | v | w | xyz | | nearest | neighborhood | node | NP | numbering |

n, k, c-expander Bipartite graph with partite sets of size n and degree at most k such that each set S with at most half the vertices of the first partite set has at least (1 + c(1-| S |/n)| S |) neighbors. [DW96] n, k, c-magnifier n-vertex graph of maximum degree k in which each set S with at most half the vertices has at least c| S | neighbors outside S . [DW96] n-ary heap A complete tree where every node has a key more extreme (greater or less) than the key of its parent. Each node has n or fewer children. [PEB00] n-ary sequence Ordered list of elements from a set of size n, with repetition allowed. [DW96] n-ary tree Rooted tree with at most n children at each internal node. [DW96]

A rooted tree in which every vertex has either 0 or m offspring. When m = 2, these are called binary trees. [WC00] A directed tree in which the out-degree of each vertex is at most n, where n is some fixed positive integer; equivalently, a rooted tree in which each vertex has at most n successors. [HC00] n-connected graph A graph whose connectivity is greater than or equal to some fixed positive integer n; i.e., a graph that remains connected even if any n – 1 edges are removed, but for which there exists a disconnecting set of n edges.[HC00] nearest neighbor algorithm The nearest neighbor algorithm is a method for solving the traveling salesperson problem. The algorithm requires following a path which always travels along the edge with the lowest weight connecting the current vertex to another which has not yet been visited. Note that the nearest neighbor algorithm will find a circuit, however, there is no guarantee that this solution will represent the minimal possible route. [DMP00] A type of greedy algorithm for combinatorial optimization problems where there is measure of nearness between neighbors. An example is the traveling salesman problem, where the procedure is to choose the next city to be one that is nearest the current city in the sequence. [HG99] nearest neighbour interchange A nearest neighbour interchange of ei = {u, v} is a transformation where one of the two subtrees adjacent to u is exchanged with one of the two subtrees adjacent to v .[CK00] nearest-insertion TSP heuristic to grow a cycle. [DW96] near-perfect matching A matching of size (n(G) – 1) / 2 . [DW96] nearly triangular embedding An embedding of a graph is nearly triangular if all but at most one region is triangular. [DA00] FIGURE

negation set An edge set whose negation makes the graph balanced. [TZ98] negative degree The number of negative incidents on the vertex. [CGM79] negative endpoint = head negative girth

The length of a shortest negative polygon. [TZ98] negative incidence If the orientation of an arc is from vertex v1 to vertex v2, then the arc is said to be negatively incident at v2 . [CGM79] neighborhood = neighbors The set of all vertices of G adjacent to the vertex v . [BW97] The vertices adjacent to a given vertex. [DW96] FIGURE

neighbors = neighborhood Nesetril-Rödl dimension problem Given a graph G = (V, E) and positive integer K ≤ | E | , is there a one-to-one function f : V → {a1 , a2 , … , ak) : 1 ≤ ai ≤ | V | for 1 ≤ i ≤ K} such that , for all u, v ∈V , (u, v) ∈ E if and only if f(u) and f(v) disagree in all K components? [GJ79] net flow At a vertex, the sum of flows on exiting edges minus the sum of flows on entering edges. [DW96] network A weighted digraph; i.e., a directed graph, each of whose arcs has been assigned a quantity (called a weight or capacity) such as a real number, vector, or tensor. The theory of networks has applications in management and engineering sciences. [HC00] A network consists of the following data:  A finite digraph G(V, E) with no self-loops and no parallel edges.  Two vertices s (the source) and t (the sink) are specified.  Each edge e ∈ E is assigned a non-negative number c(e) called the capacity of e . [SE79] network analysis problem To solve the network, i.e. to find the set of all ordered pairs (v, i) which satisfy the device characteristics and topological constraints. [HN97] network flow A vector f = [ f1 , f2 , … , fm ] of m real numbers (where m is the number of arcs in a graph G) such that  each element fi of f , which is called the flow in arc ui , is non-negative;  for every node xi of G, the sum of the flows in arcs incident to xi is equal to the sum of the flows in arcs incident from xi . [BC79]

network flow problem The network flow problem considers a graph G with a set of sources S and sinks T and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from S to T while respecting the given edge capacities. [EW00] network flows This is an assignment of arc values, called flows, say f(k) for the k-th arc, that satisfy two types of constraints:  arc bounds, L ≤ f ≤ U , and  node balances, flow out of node i − flow into node i = b(i) . The flow out of node i can be expressed as Sum k{f(k): T(k) = i} , and the flow into node i can be expressed as Sum k{f(k): H(k) = i} . If b(i) < 0 , -b(i) is a supply at node i (called a supply node); if b(i) > 0 , b(i) is a demand at node i (called a demand node). If b(i) = 0 , node i is simply a transshipment node, and the balance equation says that the flow into node i must equal the flow out of node i . Another way to express the node flow balance equations is with the node-arc incidence matrix: Mf = b . [HG99] network reliability problem Given a graph G = (V, E) , subset V ⊆V ' , a rational failure probability p(e) ,0 ≤ p(e) ≤ 1 , for each e ∈Eand a positive rational number q ≤ 1 . Assuming edge failures are independent of one another, is the probability q or greater that each pair of vertices in V ' is ed by at least one path containing no failed edge? [GJ79] network solution set The set of all ordered pairs (v, i) which satisfy the device characteristics and topological constraints. [HN97] network survivability problem Given a graph G = (V, E) , subset V ⊆V ' , a rational failure probability p(x) , 0 ≤ p(x) ≤ 1 , for each x ∈V ∪ E and a positive rational number q ≤ 1 . Assuming all edge and vertex failures are independent of one another, is the probability q or greater that for all {u, v} ∈E at least one of u, v or {u, v} will fail? [GJ79] neural network = artificial neural network A computing device which converts one or more input signals to one or more output signals by means of an interconnected set of elementary non-linear signal processors called neurons. Animal brains are examples of biological neural networks. Artificial neural networks are manmade computing devices modelled after their biological counterparts. The features which distinguish artificial neural networks from traditional Von Neumann (sequential) computers are:  the elementary processors are highly non-linear (in the limit, they are simple threshold discriminators),  the neurons are highly interconnencted which allows a high degree of parallelism and  there is no idle memory containing data and programs, but rather each neuron is pre-

programmed and continuously active. [CERN97] FIGURE

node = vertex A vertex in a directed graph. [CGM79] A vertex of a graph. In network applications, vertices are called nodes and edges are called branches. [HC00] FIGURE

node ittance matrix A matrix A Ye At , where A is the incidence matrix and Ye is diagonal matrix of edge ittances. [WM72] node block = vertex block node component = vertex component NOHO "No one hears his own information", a gossiping condition. [DW96] nonagon A polygon having nine sides. [HC00] nonahedral graph A polyhedral graph having nine vertices. [EW00] nondeterministic algorithm An algorithm for which a state may determine many next states and which follows up on each of the next states simultaneously. [MG80] Allowed to "guess" by having parallel computaion paths. [DW96] nondeterministic polynomial algorithm Polynomial-time computation paths after guessing a polynomial number of bits. [DW96] nonorientable surface A surface with only one side. [DW96] FIGURE

nonorientable genus The nonorientable genus of a graph G , h(G) , is the minimum number h such that G embeds on the surface formed by adding h crosscaps to the sphere. [DA00] nonoriented graph = undirected graph nonplanar

Having no embedding on the plane. [DW96] nonplanar graph A graph that is not planar. [ISEM00] FIGURE

nonseparable graph = biconnected component = block = biconnected graph nonsimple graph = multigraph nonterminal vertex In graph theory, a vertex of degree not equal to one. In a rooted tree, a vertex having at least one successor. [HC00] nontrivial graph A graph that is not trivial. [ISEM00] Having at least one edge. [DW96] NP The class of problems for which answers can be checked for correctness by an algorithm whose run time is polynomial in the size of the input. Note that this doesn't require or imply that an answer can be found quickly, only that any claimed answer can be verified or refuted quickly. "NP" is the class which a Nondeterministic machine accepts in Polynomial time. [PEB00] The class of problems solvable by deterministic polynomial algorithms. [DW96] NP-complete The class of problems for which answers can be checked for correctness by an algorithm whose run time is polynomial in the size of the input (it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly and a quick algorithm to solve this problem can be used to solve all other NP problems quickly. [PEB00] Problems are divided into two categories: those for which there exists an algorithm to solve it with polynomial time complexity, and those for which there is no such algorithm. We denote the former class of problems by P . There are problems for which no known algorithm exists that solves it in polynomial time, but there is also no proof that no such algorithm exists. Among these problems that are not known to be in P (or in ~P), there is a subclass of problems known as NP-complete: those for which either all are solvable in polynomial time, or none are. A fundamental member of the NP-complete class is the satisfiability problem. It is an open question whether NP = P, and most regard the NP-complete problems as having exponential time complexity. [HG99] NP-complete problem A problem which is both NP (solvable in nondeterministic polynomial-time) and NP-hard (any

other NP-problem can be translated into this problem). [EW00] NP-hard A complexity class of problems that are intrinsically harder than those that can be solved by a Turing machine in nondeterministic polynomial time. When a decision version of a combinatorial optimization problem is proven to belong to the class of NP-complete problems, which includes well-known problems such as satisfiability, traveling salesman, bin packing, etc., an optimization version is NP-hard. [PEB00] An optimization problem that relies upon the solution of an NP-complete problem. In that sense, NP-hard problems are at least as hard as NP-complete problems. Here are some NP-hard problems: • • • • • •

Bin packing Covering, Cutting stock Knapsack Packing, Partitioning, Pooling Traveling Salesman Vehicle routing

[HG99] NP-hard problem A problem is NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem (nondeterministic polynomial time) problem. NP-hard therefore means "at least as hard as any NP-problem", although it might, in fact, be harder. [EW00] NP optimization problem An NP optimization problem A is a fourtuple (I, sol, m, goal) such that  I is the set of the instances of A and it is recognizable in polynomial time.  Given an instance x of I , sol(x) denotes the set of feasible solutions of x . These solutions are short, that is, a polynomial p exists such that, for any y ∈ sol (x) ,| y | ≤ p ( | x | ) . Moreover, it is decidable in polynomial time whether, for any x and for any y such that | y | ≤ p ( | x | ) , y ∈ sol (x) .  Given an instance x and a feasible solution y of x , m(x, y) denotes the positive integer measure of y . The function m is computable in polynomial time and is also called the objective function.  goal ∈ {max, min} . [CK00] NP-problem A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine. [EW00] null flow

A flow in which all arc flows are 0. [BC79] null graph The graph with n vertices and no edges. [BW97] The empty graph containing no vertices or edges. [EW00] FIGURE

null tree  A tree which is empty.  A tree whose leaf nodes all have a null value.[PEB00] nullity The nullity N = ne – nv + ρ where ne is the number of edges, nv is the number of vertices, and ρ is the number of maximal connected subgraphs of G . [WM72] The number of edges in a coforest. [HN97] numbering A bijection between V(G) and [n(G)] .[DW96] FIGURE

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |n|

o | p | q | r | s-so | sp-sz | t | u | v | w | xyz |

| odd | offspring | operations | ordering | outdegree | obstruction Forbidden substructure. [DW96] octagon A polygon with eight sides. [HC00] octahedral graph A polyhedral graph on eight nodes. Also used to refer to the 6-vertex polyhedral graph having the connectivity of the octahedron. It has 6 nodes, 12 edges, vertex connectivity 4, edge connectivity 4, graph diameter 2, graph radius 2, and girth 3. [EW00] FIGURE

octtree A tree to index three dimensions. Each node has either eight children or no children. [PEB00] odd antihole Complement of an odd hole. [DW96]

odd component Component with an odd number of vertices. [DW96] odd cycle Cycle with an odd number of edges (vertices). [DW96] FIGURE

odd girth The length of a shortest odd polygon. [TZ98] odd graph An odd graph On is a graph having vertices given by the (n-1)-subsets of {1, … , 2n-1} such that two vertices are connected by an edge iff the associated subsets are dist. O2 is isomorphic to the complete graph K3 and O3 is the Petersen graph. [EW00] The distness graph of the k-subsets of [2k + 1] .[DW96] FIGURE

odd hole Chordless odd cycle. [DW96] FIGURE

odd vertex A vertex with odd degree. [CL96] FIGURE

odd walk Walk of odd length. [DW96] FIGURE

offspring = son = daughter If a is a vertex in a directed tree and (a, b) is an edge in the tree then vertex b is an offspring of vertex a . [SW87] one-way infinite edge sequence A sequence of edges of an infinite graph of the form v0v1 , v1 v2 , . . . . [HC00] online algorithm An online algorithm is one that obtains a solution for an online problem. Typically, this is a heuristic that obtains a "good" solution because there is not enough time to guarantee optimality. [HG99] open chain A chain with distinct endpoints. [BC79] FIGURE

open edge train

An edge train in which the initial vertex and the final vertex are distinct. [WM72] open path A path whose endpoints are distinct. [BC79] open walk Walk in which the end-vertices differ. [DW96] operations research = optimization theory The mathematical analysis of optimization problems, especially of dynamic systems subject to a given set of constraints. Applications include problems in linear and nonlinear systems, graph theory, game theory, and combinatorics.[HC00] A branch of mathematics which encomes many diverse areas of minimization and optimization. Optimization theory is the more modern term for operations research. Optimization theory includes the calculus of variations, control theory, convex optimization theory, decision theory, game theory, linear programming, Markov chains, network analysis, optimization theory, queuing systems, etc. [EW00] opposite graph A graph formed from a given digraph by exchanging the orientations of all arcs. FIGURE

optimal linear arrangement problem Given a graph G = (V, E) and positive integer K , is there a one-to-one function f : V → { 1, 2, … , | V | } such that Σ {u, v} ∈E| f(u) – f(v) | ≤ K ? [GJ79] optimal tour A solution to the traveling salesman problem or Chinese postman problem. [DW96] FIGURE

optimization problems A category of discrete mathematics which focuses on finding a best solution for a particular problem. [DMP00] optimization theory = operations research optimum communication spanning tree problem Given a complete graph G = (V, E) , weight w(e) ∈ Z0+for each e ∈ E , requirement r({u, v}) ∈ Z0+for each pair {u, v} of vertices from V and bound B∈Z0+ , is there a spanning tree T for G such that, if W({u, v}) denotes the sum of the weights of the edges on the path ing u and v in T , then Σ u, v ∈ V [W({u, v}) •r({u, v}) ] ≤ B ? [GJ79] order

The number n of vertices of G . [BW97] The cardinality of the vertex set of a graph. [CL96] A measurement of size or degree. [HC00] ordered multigraph A multigraph with an order relation (usually linear) on the edges. [DW96] ordered pair Two elements x and y from a given set, where x is designated to be the first and y the second member of the pair; equivalently, an n-tuple with n = 2. Denoted (x ,y) . In general, (x,y) ≠ (y,x) .[HC00] ordered pairs representation A representation of a graph in which edges are specified as ordered pairs (for a directed graph), or unordered pairs (for an undirected graph). [EW00] ordered tree A tree where the children of every node are ordered, that is, there is a first child, second child, third child, etc. . [PEB00] A rooted tree in which the order of the subtrees is significant. [EW00] ordering A reflexive, antisymmetric, transitive binary relation on a set X ; usually denoted ≤ . [HC00] order-preserving property Requirement that X ⊆ Y implies σ (X) ⊆ σ (Y) for a function on the subsets of a set. [DW96] order-requirement network An order-requirement network is a weighted digraph, or network, that has these characteristics:  It contains two special vertices, the starting vertex and the terminating vertex. They are usually designated by S and T . These vertices are sometimes also called the source and the sink.  No edges end at the source; no edges begin at the sink. In other words, the indegree of the source and the outdegree of the sink are 0. [ISEM00] ordinary edge A link or loop. [TZ98] FIGURE

ordinary graph Graph whose edges are links and loops only: no half or loose edges. Parallel edges are allowed. [TZ98] FIGURE

Ore graph A graph G in which the sums of the degrees of nonadjacent vertices is greater than the number of nodes n for all subsets of nonadjacent vertices. [EW00] FIGURE

Ore's theorem If a graph G has n ≥ 3 vertices such that every pair of the n vertices which are not ed by an edge has a sum of valences which is ≥ n , then G is Hamiltonian. [EW00] orientable surface A surface with two distinct sides. [DW96] orientation An assignment of a direction to each edge of a graph. A graph which has been given an orientation is called an oriented graph, and is a digraph. [WC00] FIGURE

orientation of a circuit An alternating sequence of vertices and edges of a circuit subgraph without repetitions except for the first vertex being also the last. [HN97] orientation of a crossing edge set An ordering of the end vertex sets of a crossing edge set as (V1 , V2) or (V2 , V1) . [HN97] oriented cycle A path in a graph from the certain vertex to the same vertex. FIGURE

oriented diameter problem Given a graph G = (V, E) and positive integer K ≤ | V | , can the edges of G be directed in such a way that the resulting directed graph is strongly connected and has diameter no more than K ? [GJ79] oriented graph = directed graph orthogonal drawing A graph drawing in which each edge is represented by a polyline, each segment of which is parallel to a coordinate axis. [PEB00] Otter's theorem In any tree, the number of dissimilar points minus the number of dissimilar lines plus the number of symmetry lines equals 1. [EW00] out-branching A rooted spanning tree in a directed graph, such that there is a path from the root to each vertex. [PEB00]

outdegree = exterior semidegree = outgoing degree Outdegree of a vertex v is the number of arcs in D of the form vw . [BW97] In a directed graph, we say that a vertex has outdegree x if there are (exactly) x edges leaving that vertex. [ODC00] The number of edges that are connected to vertex v and whose orientations are away from vertex v . [WM72] outerplanar graph = outplanar graph A graph that can be embedded in the plane so that all vertices lie in the boundary of the same region. [BW97] A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the unbounded outside face. [DA00] outerplane graph A particular embedding of an outerplanar graph. [DW96] out-of-kilter algorithm Applies to network flows, where the balance equations hold every iteration, but bounds and duality (optimality) conditions could be violated. The dual prices, often called potentials in this context, are modified along with flows so as to move closer to both primal and dual feasibility. [HG99] outgoing degree = outdegree outplanar graph = outerplanar graph overlap graph A graph whose vertices may be put into one-to-one correspondence with a collection of intervals on a line such that two vertices are adjacent in G if and only if their corresponding intervals overlap (not just intersect). [MG80]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |n|o|

p | q | r | s-so | sp-sz | t | u | v | w | xyz |

| partition | path | P-coloring | periodic | planted | polygon | positive | problem | pseudocut | packing number The maximum number of something findable in a graph without violation some condition P . [DW96] page

One of the outerplanar subgraphs in a book embedding. [DW96] A closed half-plane. [DA00] pagenumber = book thickness Minimum number of pages in a book embedding. [DW96] The pagenumber of a graph G , pn(G) , is the fewest number of pages in a book containing G . [DA00] Paley graph = quadratic residue graph A subgraph of the complete graph Kq in which each vertex has degree (q – 1)/2 . [BW97] FIGURE

panconnected graph A connected graph G of order n is called panconnected if for every pair u , v of distinct vertices of G , there exists a u-v path of length l for each l satisfying d(u, v) ≤ l ≤ n . [CL96] pancyclic graph A simple graph on n vertices is pancyclic if it contains cycles of all lengths 3, 4,..., n . [SL99] A connected graph G of order n ≥ 3 is called pancyclic if G contains a cycle of length l for each l satisfying 3 ≤ l ≤ n .[CL96] FIGURE

parallel arcs Arcs having the same endpoints. [CGM79] parallel edges Edges with the same endpoints. [HN97] FIGURE

parallel elements Non-loops in a matroid that form a set of rank 1. [DW96] parent An item of a tree which refers to one or more child items which are conceptually on the next level "down" or farther from the root. [PEB00] FIGURE

parity Odd or even. [DW96] parity subgraph Subgraph H such that dH(v) ≡ dG(v) mod 2 for all v ∈ V(G) .[DW96] partial edge set problem Given a graph G = (V, E) , positive integers

K ≤ | E | and L ≤ | V | , is there a subset E ' ⊆ E with | E ' | ≤ K such that E ' contains at least one edge from every circuit of length L or less in G ? [GJ79] partial graph A graph which is left after removing from the graph a subset of its arcs. [BC79] partial order dimension problem Given acyclic digraph G = (V, A) that is transitive, does there exist a collection of k ≤ K linear orderings of V such that (u, v) ∈A if and only if u is less than v in each of the orderings? [GJ79] partially dynamic graph problem Problem where the update operations include either edge insertions (incremental) or deletions (decremental). [PEB00] partially orderable graph = comparability graph partite set Block of a vertex partition, often called a "part" of a k-partite graph. [DW96] partition A collection of pairwise dist subsets whose union is S . [HN97] partition into cliques problem Given a graph G = (V, E) and positive integer K ≤ | V | , can the vertices of G be partitioned into k ≤ K dist sets V1 , V2 , … , Vk such that, for 1 ≤ i ≤ k , the subgraph induced by Vi is a complete graph? [GJ79] partition into forests problem Given a graph G = (V, E) and positive integer K ≤ | V | , can the vertices of G be partitioned into k ≤ K dist sets V1 , V2 , … , Vk such that, for 1 ≤ i ≤ k , the subgraph induced by Vi contains no circuits? [GJ79] partition into Hamiltonian subgraphs problem Given a graph G = (V, E) and a positive integer K ≤ |V| , can the vertices of G be partitioned into k ≤ K dist sets V1 , V2 , … , Vk such that, for 1 ≤ i ≤ k , the subgraph induced by Vi contains a Hamiltonian circuit? [GJ79] partition into isomorphic subgraphs problem Given graphs G = (V, E) and H = (V ' , E ' ) with | V | = q | V ' | for some q∈Z+ , can the vertices of G be partitioned into q dist sets V1 , V2 , … , Vq such that, for 1 ≤ i ≤ q , the subgraph of G induced by Vi is isomorphic to H ? [GJ79] partition into paths of length 2 problem

Given a graph G = (V, E) with | V | = 3q for a positive integer q , is there a partition of V into q dist sets V1 , V2 , … , Vq of three vertices each so that, for each Vi = {vi[1] , vi[2] , vi[3]} , at least two of the three edges {vi[1] , vi[2]} , {vi[1] ,vi[3]} and {vi[2] , vi[3]} belong to E ? [GJ79] partition into perfect matchings problem Given a graph G = (V, E) and positive integer K ≤ | V | , can the vertices of G be partitioned into k ≤ K dist sets V1 , V2 , … , Vk such that, for 1 ≤ i ≤ k , the subgraph induced by Vi is a perfect matching? [GJ79] partition into triangles problem Given a graph G = (V, E) with |V| = 3q for a positive integer q , is there a partition of V into q dist sets V1 , V2 , … , Vq of three vertices such that for each Vi = {vi[1] , vi[2] , vi[3]}, the three edges {vi[1] , vi[2]}, {vi[1] ,vi[3]} and {vi[2] , vi[3]} all belong to E ? [GJ79] partition matroid Matroid induced by a partition of the ground set in which a set is independent if and only if it has at most one element from each block of the partition. [DW96] partitionable graph Graph with aw + 1 vertices such that each graph formed by deleting one vertex is colorable by w stable sets of size a and coverable by a cliques of size w. [DW96] party problem = maximum clique problem path = chain A sequence of vertices from one vertex to another using the arcs. The length of a path is the number of arcs used, or the number of vertices used minus one. A simple path cannot visit the same vertex twice. A closed path has the same first and last vertex. More formally, a path is a sequence of vertices in a digraph of the form {x0 , x1 , ..., xn} such that xi and xi+1 are adjacent for i = 0, ... , n – 1 . In a simple path all the xi are distinct. In a closed path, x0 = xn . Path is used by some authors to mean a simple chain in a graph. [WC00] A finite alternating sequence of distinct vertices and edges v0 , e1 , v1 , e2 , . . . , vk-1 , ek , vk in a graph such thatvi-1 and vi are the end vertices of the edge ei , 1 ≤ i≤ k . Equivalently, a trail with distinct vertices. [HC00] A chain (more commonly called a path ) in a graph is a sequence {x1 , x2 , x3 , ... , xk} of nodes such that {[x1 , x2], [x2 , x3], ... , [xk-1 , xk]} are edges of the graph. In a non-simple graph (one with repeated edges) it is necessary to impose the condition that no edge occur in the sequence more than it's repetition number. In a simple graph, each edge can appear at most once. [ODC00] A route in a graph with all edges distinct.

FIGURE

path addition A step in an ear decomposition. [DW96] path constrained network flow problem Given a digraph G = (V, A) , specified vertices s and t , capacity c(a) ∈Z+for each a ∈A , a collection P of directed paths in G and a requirement R∈Z+ , is there a function g : P→Z0+ such that if f : A →Z0+is the flow function defined by f(a) = Σ p ∈ P(a) g(p) , where P(a) ⊆P is the set of all paths in P containing the arc a , then f is such that  f(a) ≤ c(a) for each a ∈ A ,  for each v ∈ V – {s, t} , flow is conserved at v ,  the net flow into t is at least R ? [GJ79] path decomposition Expression of a graph as a union of edge-dist paths. [DW96] FIGURE

path distinguishers problem Given acyclic digraph G = (V, A) , specified vertices s, t∈V and positive integer K ≤ | A | , is there a subset A ' ⊆ A with | A' | ≥ K such that for any pair p1 , p2 of paths from s to t in G , there is some arc in A' that is in one of p1 and p2 but not both? [GJ79] path graph The intersection graph of a family of paths in a tree. [MG80] A tree with two nodes of valency 1, and the other nodes of valency 2. [EW00] FIGURE

path graph completion problem Given a graph G = (V, E) and non-negative integer K , is there a superset E ' containing E such that | E – E ' | ≤ K and the graph G ' = (V, E ' ) is the intersection graph of a family of paths on an undirected tree? [GJ79] path system accessibility problem Given a finite set X of nodes, a relation R ⊆ X × X× X and two sets S , T⊆X of source and terminal nodes, is there and accessible terminal node? [GJ79] path with forbidden pairs problem Given a digraph G = (V, A) , specified vertices s, t ∈ V , collection C = {(a1 , b1) , … , (an , bn)} of pairs of vertices from V , is there a directed path from s to t in G that contains at most one vertex from each pair in C ? [GJ79]

Patricia tree A compact representation of a trie where all nodes with one child are merged with their parents. [PEB00] P-coloring A vertex partition into subsets inducing graphs with property P . [DW96] p-critical graph An imperfect graph whose proper induced subgraphs are all perfect. [DW96] pendant edge A bridge incident with an end-vertex. [CL96] FIGURE

pendant vertex = leaf pentagon A polygon with five sides, usually convex. [HC00] pentahedral graph A polyhedral graph on five nodes. There are two topologically distinct pentahedral graphs, corresponding to the skeletons of the square pyramid and triangular dipyramid. [EW00] FIGURE

perceptron This term is sometimes used to refer to a single McCulloch-Pitts neuron, but may also refer to a network of neurons in which the output(s) of some neurons are connected through weighted connections to the input(s) of other neurons. [CERN97] percolation network A (usually infinite) network whose edges have been randomly assigned values of 1 or 0 (called conducting or insulating links, respectively). The percolation problem for a given network is to determine the number or concentration of conducting links required for the network to become conducting. [HC00] percolation theory Percolation theory deals with fluid flow (or any other similar process) in random media. If the medium is a set of regular lattice points, then there are two types of percolation. A site percolation considers the lattice vertices as the relevant entities; a bond percolation considers the lattice edges as the relevant entities. [EW00] percolation threshold The critical fraction of lattice points which must be filled to create a continuous path of nearest neighbors from one side to another. [EW00] perfect 1-factorization

A 1-factorization is perfect if the union of any two 1-factors (color classes) is a Hamilitonian cycle. [DA00] perfect elimination ordering Deletion order such that each deleted vertex is adjacent to remaining vertices in a balanced way. [DW96] perfect graph A graph G is called perfect if the chromatic number χ (H) and the clique number ω (H) are equal, χ (H) = ω (H) , for each induced subgraph H of G . [CL96] A simple graph G such that, for every vertex-induced subgraph H of G, if m is the largest integer for which there is a subgraph of H isomorphic to the complete graph Km , then m is at most the chromatic number of H . [HC00] A graph G such that for every induced subgraph of G, the size of the largest clique equals the chromatic number. [EW00] FIGURE

perfect matching = 1-factor A matching of a graph containing n / 2 edges, the largest possible. [EW00] An independent edge set that includes every vertex of G . [BW97] A perfect matching or 1-factor in a graph is a collection of edges which together are incident with every vertex exactly once. [DA00] FIGURE

perfectly weighted tree If G is a weighted tree with weights wi > 1 assigned to each vertex vi , then G is perfectly weighted if the matrix MG = diag(wi) – adj(G) , where adj(G) is the adjacency matrix of G . [EW00] periodic graph = dynamic graph Covering graph of a (finite) gain graph whose gains are in the additive group Zd for some d > 0. [TZ98] peripheral vertex = peripheral point A node in a graph for which the graph eccentricity equals the graph diameter. [EW00] periphery A subgraph of G induced by its peripheral vertices. [CL96] permutation gain graph = permutation voltage graph Gain graph whose gain group is a permutation group. [TZ98] permutation signed graph Like a permutation gain graph but with signs instead of gains. [TZ98]

permutation voltage graph = permutation gain graph PERT chart = activity network diagram Labeled network with weights assigned to the arcs. The arcs of a PERT chart (Project Evaluation and Review Technique) correspond to activities needed for the implementation of a project and nodes are events occuring during the project's life cycle. A finite digraph G(V, E) with the following properties:  There is a start vertex s and a termination vertex t≠ s .  G has no directed circuits.  Every vertex v ∈ V – {s, t} is on some directed path from s to t . [SE79] FIGURE

Petersen graph The complement of the line graph of K5 . [BW97] A graph on ten vertices; all nodes have degree three. [ODC00] FIGURE

Petersen's theorem Every cubic graph with no cut edges has a perfect matching. [HC00] Petri net A graphical representation of concurrent systems in of tokens, places and transition bars. [CERN97]

Abstract model used to represent parallel systems and processes. Typically described using directed graphs (i.e. graphs whose edges are depicted by arrows showing a direction of information flow). More precisely, a petri net is a seven-tuple (P, T, V, f, g, N, m), where  P is a nonempty finite set of nodes,  T is a nonempty finite set of transitions,  V is a valuation space {0, 1},  f is a binary function used in determining the connections from nodes to transitions (i.e. f : P × T – V , and if f ( p, t ) = 1 then node P connects to transition T , otherwise not),  g is a binary function used in determining the transitions to connect to nodes (i.e. g : T × P – V and a connection is made from t to p if and only if g ( t, p ) = 1),  N is a set of markings {0,1,2,...}, and  m is the initial marking function, m: P – N .[CNA96]  FIGURE pit A balanced polygon with no balanced chord. [TZ98] planar graph A graph that can be drawn on a plane so that its edges intersect only at their end vertices; i.e., a

graph that can be embedded on a plane. [HC00] A graph which has a representation in the plane as a plane graph. [SE79] FIGURE

planar straight line graph A graph embedding of a planar graph in which only straight line segments are used to connect the vertices. [EW00] FIGURE

planar subgraph problem Given a graph G = (V, E) and positive integer K ≤ | E |, is there a subset E ' ⊆ E with | E ' | ≥ K such that the subgraph G ' = (V, E ' ) is planar? [GJ79] planarization The process of transforming a graph into a planar graph. More formally, the transformation involves either removing edges (planarization by edge removal), or replacing pairs of nonincident edges by 4-stars (planarization by adding crossing vertices). In both cases, the aim of planarization is minimize the number of edge removals or replacements. [PEB00] plane A surface S with the property that the straight line ing any two points of S is also contained in S . [HC00] plane graph A drawing of a graph in the plane in such a way that each vertex is represented by a point and each edge is represented by a continuous line connecting the two points which represent its end vertices and no two lines, which represent edges, share any points except in their ends. [SE79] A planar graph that has been drawn on the plane. [HC00] FIGURE

plane tree A tree embedded in the plane. [BW97] FIGURE

planted planar tree = planted plane tree A planted plane tree (V, E, v, α ) is defined as a vertex set V, edge set E, root v, and order relation α on V which satisfies:  For x, y ∈ V if ρ (x) < ρ (y) , then xα y , where ρ (x) is the length of the path from v to x ;  If {r, s}, {x, y} ∈ E , ρ (r) = ρ (x) = ρ (s) – 1 = ρ (y) – 1 and r α x , then sα y . [EW00] planted plane tree = planted planar tree planted tree

A rooted tree in which the root has degree 1. [BW97] FIGURE

Plateau's problem The problem in calculus of variations to find the minimal surface of a boundary with specified constraints (usually having no singularities on the surface). In general, there may be one, multiple, or no minimal surfaces spanning a given closed curve in space. The problem is named for the Belgian physicist who solved some special cases experimentally using soap films and wire frames. [EW00] Platonic graph The graphs corresponding to the vertices and edges of the five regular solids – the tetrahedron, cube, octahedron, dodecahedron and icosahedron. [BW97] FIGURE

Platonic solids The five three-dimensional regular polytopes: the regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron. [ODC00] point connectivity = connectivity point lattice A regularly spaced array of points falling along regularly spaced line. The grid lines can be oriented to form unit cells in the shape of a square, rectangle, hexagon, etc. However, unless otherwise specified, point lattices are generally taken to refer to points in a square array, i.e., points with coordinates (m, n, …) , where m, n, ... are integers. Such an array is often called a grid or a mesh. Point lattices are frequently simply called "lattices". [EW00] point of articulation = cut vertex point on periphery A vertex with maximum separation. [CGM79] poise gains Gains in Z whose value on a directed edge is 1 in the edge's direction (thus, -1 in the opposite direction) and on an undirected edge is 0. [TZ98] polar graph Graph with a polarity. [TZ98] polarity An assignment to each vertex of two poles, each edge end belonging (or "being incident") to one pole. [TZ98] polygon A closed plane figure having straight sides. A regular polygon has equal sides and equal angles.

[PR98] polygon graph = circuit graph A connected graph with each vertex having degree two. [HN97] FIGURE

polyhedral graph = c-net An n-polyhedral graph (sometimes called a c-net) is a 3-connected simple planar graph on n nodes. Polyhedral graphs are sometimes simply known as "polyhedra" (which is rather confusing since the term "polyhedron" more commonly refers to a solid with faces, not vertices). [EW00] FIGURE

poly-killer graph Minimal subgraph with the property that it cannot occur in any graph with a polyhedral embedding. [DA00] polymatroid Let N be a finite set and let f be a submodular function on the subsets of N with f(Ø) = 0 . The polymatroid associated with (N, f) is the polytope: {x in R n: Sum j{xj: j∈ S} ≤ f(S) for all S∈ N} . [HG99] polymatroid rank function A submodular function that takes zero value on 0 and is nonnegative and increasing. [HN97] polynema A polynema of order n is Kyrmse's term for a connected graph having n edges. An n-polynema must therefore have either n or n + 1 nodes. [EW00] FIGURE

polynomial  Any function which is the sum of constants times powers of the argument: f (x) = Σ ci xpi .  In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polynomial function of the problem size, n . [PEB00] polynomial time When the execution time of a computation, m(n) , is no more than a polynomial function of the problem size, n . More formally m(n) = O(nk) where k is a constant. [PEB00] polynomial time algorithm An algorithm whose time complexity function is O(p(n)) for some polynomial function p , where n is used to denote the input length. [GJ79] The most efficient algorithms which can be solved in time c nk , for some constants c and k . [BW97] polynomial-bounded algorithm

An algorithm running time of which is bounded by a function of order sk , where s is the problem size and k is a constant. [BC79] positive cycle problem Given a signed digraph, does it contain a positive cycle? [TZ98] positive degree The number of positive incidents at the vertex. [CGM79] positive endpoint = tail The first element of the ordered pair of vertices in a directed graph, tail of the arrow. [HN97] positive incidence If the orientation of an arc is from vertex v1 to vertex v2, then the arc is said to be positively incident at v1. [CGM79] potential vector A vector λ that assigns a value to each node of G from which a voltage vector v can be derived: v = A λ , where A is an incidence matrix of G . [HN97] power set The set of all sets. [BC79] power variables The variables in a bond graph that are forced to be identical when two multiports are connected. The product of the two power variables (effort and flow) considered as functions of time is the instantaneous power flowing between the two multiports. [KMR90] P-problem A problem is assigned to the P (polynomial time) class if the number of steps is bounded by a polynomial. [EW00] predecessor A vertex x in a directed graph is called a predeccessor of another vertex y if there is an edge directed from x to y . [RND77] FIGURE

primal graph The dual of the dual graph. [CGM79] prime-distance graph A distance graph with distance set given by the set of prime numbers. [EW00] primitive graph A graph is said to be primitive if there exists an integer m such that there is a chain of length m

from each vertex vi to every other vertex vj . [CGM79] FIGURE

Prim's algorithm An algorithm for computing a minimum spanning tree. It builds upon a single partial minimum spanning tree, at each step adding an edge connecting the vertex nearest to but not already in the current partial minimum spanning tree. [PEB00] problem A question to be answered, a requirement to be fulfilled, or a best possible situation or structure to be found. [MG80] problem size A measure of the amount of input data. [BC79] procedure A specific prescription for carrying out a task or solving a problem. Also called an algorithm, method, or technique. [EW00] projective plane A projective plane is derived from an affine plane by the addition of points "at infinity". [ODC00] FIGURE

proper ancestor If there is a nonempty path (i.e., x ≠ y) from vertex x to vertex y in a directed spanning tree, we say that x is an proper ancestor of y . [RND77] proper coloring A vertex coloring or edge coloring of a graph in which no two adjacent vertices or edges have the same color. [PEB00] FIGURE

proper cover A cover of a set X which does not contain the entire set X itself as a subset. [EW00] proper cutset A minimal cutset. [CGM79] FIGURE

proper descendant If there is a nonempty path (i.e., x ≠ y) from vertex x to vertex y in a directed spanning tree, we say that y is an proper descendant of x. [RND77] proper subgraph A subgraph of G not identical to it. [HN97]

proper subset Any subset of A which is not equal to A . [BC79] P-set cycle A subgraph which is either a directed circuit or a VDU of directed circuits and which contains all vertices in a given oriented graph. [WM72] pseudocut A set of edges equal to U = S ⊕ (e') where S is either a cutset containing edge e' or the empty set. [WM72] pseudodigraph A digraph with parallel arcs and loops. [CL96] pseudograph Informally, a pseudograph is a graph with multiple edges (or loops) between the same vertices (or the same vertex). Formally: a pseudograph is a set V of vertices along, a set E of edges, and a function f from E to {{u, v} | u, v in V} . (The function f shows which vertices are connected by which edge.) An edge is a loop if f(e) = {u} for some vertex u in V. [CC99] A non-simple graph in which both loops and multiple edges are permitted. [EW00] Generalization of a multigraph, in which besides the multiple edges also loops (edges (a, a)) are permitted. FIGURE

pseudosymmetrical graph A graph is pseudosymmetrical if the number of arcs directed away from any vertex is the same as the number of arcs directed toward it. [CGM79] P-tree  A spatial access method that defines hyperplanes, in addition to the orthogonal dimensions, which node boundaries may parallel. Space is split by hierarchically nested polytopes (multidimensional boxes with nonrectangular sides). The R-tree is a special case which has no additional hyperplanes.  A spatial access method which splits space by hierarchically nested polytopes. The R-tree is a special case in which all polytopes are boxes. [PEB00]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |n|o|p|

q | r | s-so | sp-sz | t | u | v | w | xyz |

quadratic assignment The objective is a quadratic form, which can have just cross , so it need not be convex (in fact, it can be quasiconcave, in which case a solution occurs at an extreme point). The QAP includes the traveling salesman problem as a special case (this is what is used with a neural network model of the TSP). [HG99] quadratic residue graph = Paley graph quadtree A tree having four branches at each node. Quadtrees are used in the construction of some multidimensional databases (e.g., cartography, computer graphics, and image processing). [EW00] A tree where each node is split along all d dimensions, leading to 2d children. [PEB00] quartic graph A 4-regular graph. The unique quartic graph on five nodes is the complete graph K5 . [EW00] FIGURE

quintic graph A 5-regular graph. The only quintic graph on n ≤ 7 nodes is the complete graph K6 . [EW00] FIGURE

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |n|o|p|q|

r | s-so | sp-sz | t | u | v | w | xyz |

| radius | red | restriction | root | rural | R-tree A spatial access method which splits space with hierarchically nested, and possibly overlapping, boxes. The tree is height-balanced. [PEB00] R+-tree A spatial access method which splits space with hierarchically nested boxes. Objects are indexed in each box which intersects them. The tree is height-balanced. [PEB00] R*-tree A spatial access method which splits space in hierarchically nested, possibly overlapping, boxes. The tree is height-balanced. It is similar to the R-tree, but reinserts entries upon overflow, rather than splitting. [PEB00] radius = graph radius Minimum of the maximum distances associated with the vertices of a graph. [CGM79]

The minimum eccentricity among the vertices of a graph G. [CL96] Ramsey number For positive integers s and t , the Ramsey number r(s, t) is the least positive integer n such that G contains either s mutually adjacent vertices or an independent set of t vertices. [CL96] The minimum number of vertices v = R (m, n) such that all undirected simple graphs of order v contain a clique of order m and an independent set of order n . The Ramsey number gives the solution to the party problem, which asks the minimum number of guests that must be invited so that at least m will know each other or at least n will not know each other. [EW00] The Ramsey number r(k1 , ... , km) is the minimum integer n such that every m-edgecolouring of Kn contains a complete subgraph on kivertices, with all edges of colour i , for some i . [SL99] Ramsey theory The mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large. Ramsey theory is named after Frank Plumpton Ramsey, who did seminal work in this area before his untimely death at age 26 in 1930. [EW00] random Boolean network A random Boolean network of size k generalizes the basic binary Cellular Automata model by evolving each site variable xi = 0 or 1 according to a randomly selected Boolean function of k inputs. Since there are two choices for every combination of states of the k inputs at each site, the Boolean function is randomly selected from among the 22n possible Boolean functions of k inputs. This model was first introduced by Kauffman in 1969 in a study of cellular differentiation in a biological system (binary sites were interpreted as elements of an ensemble of genes switching on and off according to some set of random rules). Since its conception, however, related models have found wide application in an increasingly large domain of diverse problems. Such models of strongly disordered systems exhibit remarkable and unexpected order. [CNA96] random graph A graph that has vertices v1, v2, … , vn and possible edges occur independently, each with probability p . [BW97] The probability space whose elements are different labelled graphs with vertex set {v1 , v2 , …. , vn} . [CL96] A random graph is a graph in which properties such as the number of nodes, edges, and connections between them are determined in some random way. [EW00] FIGURE

randomized binary search tree A binary search tree in which nodes have a randomly assigned priority. Updates keep priorities in heap order instead of keeping balance information and doing rebalance

operations. [PEB00] rank function of a matroid The rank function of a matroidM = (S, I) is a function r from the set of subsets of S to the set of integers, defined by r(A) = max{|X|: X⊆A and X∈I}, for every subset A of S . [SL99] rank of a graph The rank of a graph R = nv − ρ , where nv is the number of vertices and ρ is the number of maximal connected subgraphs in the graph. [WM72] rank of a matroid The rank function of a matroidM = (S, I) is a function r from the set of subsets of S to the set of integers, defined by r(A) = max{|X|: X ⊆A and X∈I} , for every subset A of S . The rank of the matroid M , denoted r(M) , is the rank of S . [SL99] rank polynomial For a graph G, possibly containing loops and multiple edges, we define the rank polynomial R(G; x, y) by the following properties: R(G; x, y) = (1 + y) R(G - e; x, y) if e is a loop, R(G; x, y) = (1 + x) R(G.e; x ,y) if e is a cut edge, R(G; x, y) = R(G - e; x, y) + R(G.e; x, y) otherwise; and R(G; x, y) = 1 if G has no edges. [SL99] r-branching Branching rooted at r . [DW96] reachable A vertex v is reachable from another vertex u if there is a path of any length from u to v . [PEB00] FIGURE

realizable graph = embeddable graph A graph G is realizable or embeddable on a surface S if G can be drawn on S so that edges (more precisely, the curves corresponding to edges) intersect only at a vertex (a point, corresponding to a vertex) mutually incident with them. [CL96] rectilinear crossing number The minimum number of crossings in a straight line drawing of a graph in a plane. [EW00] rectilinear Steiner tree A minimum-length rectilinear tree connecting a set of points, called terminals, in the plane. This tree may include points other than the terminals, which are called Steiner points. [PEB00] recursion

A recursive process is one in which objects are defined in of other objects of the same type. Using some sort of recurrence relation, the entire class of objects can then be built up from a few initial values and a small number of rules. [EW00] recursive algorithm A recursive algorithm is one that calls or makes use of itself. An important part of a recursive algorithm is a termination condition that, once it is met, will cause the algorithm to cease calling itself and stop. [ISEM00] red-black tree = symmetric binary B-tree = SBB tree A nearly-balanced tree which uses an extra bit per node to maintain balance. No leaf is more than twice as far from the root as any other. [PEB00] An extended binary tree satisfying the following conditions:  Every node has two children, each colored either red or black.  Every leaf node is colored black.  Every red node has both of its children colored black.  Every path from the root to a leaf contains the same number (the "black-height") of black nodes. [EW00] FIGURE

reduced graph If an edge e is removed from a given graph G , the resulting graph, denoted G ' (e) is referred to as a reduced graph. [WC00] reduced incidence matrix A matrix obtained from an incidence matrix of G by omitting one row belonging to each component of G. [HN97] reducible problem = transformable problem reentrant circuit A graph cycle which terminates at the starting point. [EW00] reference vertex The vertex corresponding to the row in an exhaustive incidence matrix which has been deleted. [WM72] region = face sufficiency problem Given acyclic digraph G = (V, A) and positive integer K , is there a computation for G that uses K or fewer s? [GJ79] regular graph A graph in which all vertices have the same degree. [CGM79]

A graph is said to be regular of degree r if all local degrees are the same number r . A 0regular graph is an empty graph, a 1-regular graph consists of disconnected edges, and a 2regular graph consists of disconnected cycles. The first interesting case is therefore 3regular graphs, which are called cubic graphs . Similarly, 4- and 5-regular graphs are called quartic and quintic graphs, respectively. [EW00] FIGURE

regular map A map on a surface is regular if the order of the automorphism group of the map is 2 | E(G) | for oriented surfaces and 4 | E(G) | for nonorientable surfaces. Regular maps have the largest possible automorphism groups over all embeddings of a graph (in the orientable case the embedding must preserve an orientation of the surface). [DA00] regular spanning graph A polygonal regular graph whose dual graph is also regular. restriction The restriction to an edge set S is the spanning subgraph whose edge set is the specified set. [TZ98] return arc An arc of infinite capacity which s the source and sink of the network. [BC79] Riddell's formula Riddell's formula for unlabeled graphs is the Euler transform relating the number of unlabeled connected graphs on n nodes satisfying some property with the corresponding total number (not necessarily connected) of graphs on n nodes. Riddell's formula for labeled graphs is the exponential transform relating the number of labeled connected graphs on n nodes satisfying some property with the corresponding total number (not necessarily connected) of labeled graphs on n nodes. [EW00] right-threaded tree A variant of a threaded tree in which only the right thread, i.e. link to the predecessor, of each node is maintained. [PEB00] rigid graph A framework (or graph) is rigid iff continuous motion of the points of the configuration maintaining the bar constraints comes from a family of motions of all Euclidean space which are distance-preserving. [EW00] ring product The ring product A ⊗ B = min {α p⊕ β q ; α p ∈A , β q ∈B} , where A and B are collections of sets. [WM72] ring sum of graphs G1 ⊕ G2 : the union of graphs minus the intersection of graphs, G1⊕G2 = (G1∪G2) –

(G1∩G2) . [WM72] r(n)-approximate algorithm Let A be an NPO problem and let T be an algorithm that, for any instance x of A , returns a feasible solution T(x) of x . Given an arbitrary function r : N → (1,  ) , we say that T is an r(n)-approximate algorithm for A if, for any instance x , the performance ratio of the feasible solution T(x) with respect to x verifies the following inequality: R(x, T(x)) ≤ r ( | x | ) . If an NPO problem its an r(n)-approximate polynomial-time algorithm we say that it is approximable within r(n) . [CK00] Robertson graph The unique (4, 5)-cage graph, which has 19 vertices. [EW00] FIGURE

Robertson-Seymour theorem A generalization of the Kuratowski reduction theorem by Robertson and Seymour, which states that the collection of finite graphs is well-quasi-ordered by minor embeddability, from which it follows that Kuratowski's "forbidden minor'' embedding obstruction generalizes to higher genus surfaces. [EW00] root = eve = endpoint The distinguished initial or fundamental item of a tree. The only item which has no parent. [PEB00] A vertex in a directed tree from which there is a path to all other vertices of a tree. [CGM79] A fixed vertex of a tree. FIGURE

root of a digraph A digraph G(E, V) is said to have a root r if r∈V and every vertex v ∈V is reachable from r . [SE79] FIGURE

root vertex A vertex v in a directed graph G such that there are directed paths from v to all the remaining vertices of G . If G is a tree, there is at most one root vertex; if there is a root vertex in a tree G , it has indegree zero and every other vertex of G has indegree one. [HC00] FIGURE

rooted forest A graph in which each component is a rooted tree. [BW97] FIGURE

rooted graph A graph with one vertex distinguished from the rest. The distinguished vertex is called a

root. [BW97] FIGURE

rooted tree = directed tree = arborescence A tree in which one vertex has been distinguished. The distinguished vertex is called the root of the tree. [WC00] A directed graph for which the associated undirected graph is a tree and for which there is a unique vertex of indegree 0. [SW87] A digraph D is an arborescence if there is a distinguished node x (called the root) and for every node y different from x there is exactly one elementary path from x to y . [ODC00] FIGURE

rooted tree arrangement problem Given a graph G = (V, E) and positive integer K , is there a rooted tree T = (U, F) with | U | = | V | and a one-to-one function f : V→U such that for every edge {u, v} ∈Ethere is a simple path from the root that includes both f(u) and f(v) and such that if d(x, y) is the number of edges on the path from x to y , then Σ {u, v} ∈E d( f(u), f(v)) ≤ K ? [GJ79] rotation The collection of local rotations is called a rotation. Rotations are well known to correspond 1-1 with embeddings of Kn in an oriented surface. [DA00] route An n-route is defined as a walk of length n with specified initial point in which no line succeeds itself. [EW00] A finite sequence of edges of a graph (a0, a1), (a1, a2), … , (an-1, an) connecting the vertices a0 and an and ing the vertices a1 , a2 , … , an-1 . routing problem Finding a path or cycle in a network. An easy routing problem is the shortest path; a hard one is the TSP. One prevalent class, with many variations, is vehicle routing. [HG99] r-regular digraph A digraph D is called r-regular or regular of degree r if outdegree v = indegree v = r . [CL96] r-regular graph A graph where degree v = r for all vertices (outdegree v = indegree v = r in case of a digraph). r-staset Stable set of size r. [DW96] rural postman problem

Given a graph G = (V, E) , weight w(e) ∈Z0+ for each e ∈E , subset E ' ⊆E and bound B∈Z+ , is there a circuit in G that includes each edge in E ' and that has total length no more than B ? [GJ79]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | |n|o|p|q|r|

s-so | sp-sz | t | u | v | w | xyz |

| saturated | search | set | shortest | signed | simple | skeleton | source | s, t-numbering A numbering of the vertices of a graph such that from each vertex there is a path to s through successfully lower-indexed vertex and a path to t through successively higher-indexed vertices. [DW96] sandwitch theorem The Lovasz number γ (G) of a graph G satisfies ω (G) ≤ γ (G) ≤ χ (G) , where ω (G) is the clique number and χ is the minimum number of colors needed to color the vertices of G . [EW00] satisfaction = balance satisfied = balanced saturated arc An arc in the flow network in which the flow is equal to the capacity. [BC79] saturated edge An edge in a flow network which has the maximum possible flow. [PEB00] saturated vertex A vertex in a graph which is on an edge of a matching is said to be saturated. Given a matching M , if X is a set of vertices saturated by M , then M is said to be an X-saturating matching. [WC00] SBB tree = red-black tree scapegoat tree A binary search tree which needs no balance information. Search time is logarithmic, and the amortized cost of update is logarithmic. [PEB00] Schlegel graph A graph corresponding to polyhedra skeletons. [EW00]

FIGURE

S-component Subgraph of G induced by S ∪ Vi , where Vi is the vertex set of a component of G – S . [DW96] score sequence The score sequence of a tournament is a monotonic nondecreasing sequence of the outdegrees of the vertices. [EW00] SDR = system of distinct representatives = transversal search tree The tree formed by a branch and bound algorithm strategy. It is a tree because at each (forward) branching step the problem is partitioned into a disjunction. A common one is to dichotomize the value of some variable, x ≤ v or x ≥ v + 1. This creates two nodes from the parent: left child and right child. [HG99] search tree property When the key of every node of a binary tree is larger than the key of its left child and smaller than its right child. [PEB00] Seidel matrix A n × n matrix S = Jn – 2A – In , where Jn is n× n all-1 matrix, A is the adjacency matrix, and In is n × n unity matrix. [BW97] Seidel switching = graph switching Seidel switching class = switching class self-complementary graph A graph which is isomorphic to its graph complement. [EW00] FIGURE

self-loop = loop semicycle The semiwalk is called a semicycle if u0 = uk , where k ≥ 3 , and the vertices u0 , u1 , … , uk are distinct. [CL96] semimodular function Submodular or supermodular function. [HN97] semipath The u-v semiwalk is a u-v semipath if the vertices u0 , u1 , … , ukare distinct. [CL96]

semiwalk A u-v semiwalk in a digraph D is a finite, alternating sequence u = u0 , a1 , u1 , a2 , … , uk-1 , ak , uk = v of vertices and arcs, beginning with u and ending with v, such that either ai = (ui-1 , ui) or ai = (ui , ui-1) for i = 1, 2, … , k . [CL96] separable graph A graph that is not connected or has at least one cut vertex; equivalently, a graph of connectivity at most 1. [HC00] A connected graph is said to be separable if there exists a vertex p and a way to cut the vertex into two such that the graph becomes separated without producing isolated vertices. [WM72] A graph that contains an articulation point. [RND77] FIGURE

separating edge An edge of a graph is separating if a path from a point A to a point B must over it. Separating edges can therefore be viewed as either bridges or dead ends. [EW00] An edge which deletion causes the increase of the number of components of a graph. FIGURE

separating set of vertices = vertex cut separator The union of elementary separators. [HN97] sequential graph A connected graph having n edges is said to be sequential if it is possible to label the nodes i with distinct integers fi in {0, 1, 2, … , n – 1} such that when edge (i, j) is labeled fi + fj , the set of edge labels is a block of n consecutive integers. [EW00] series edges Let endpoints of edge e1 be u1 and u2 and endpoints of edge e2 be v1 and v2 where u1 ≠ u2 and v1 ≠ v2 .Then e1 and e2 are said to be in series if u2 = v1 and no other edges have u2 as their endpoints. [WM72] series-reduced tree = topology tree set = collection A group specified by the elements (or ) that belong to it. [HN97] set of fundamental circuits Let {e1 , e2 , … , en(E) - n(V) - 1} be a set of chords with respect to a tree t of a connected graph. Also let Ci be a circuit in t ∪(ei ) for i = 1, 2, … , n(E) – n(V) – 1 . Then the collection of circuits {C1 , C2 , … , Cn(E) - n(V) - 1} is called a set of fundamental circuits with respect to a tree t . [WM72]

The set of all fundamental cycles with respect to a tree T . There are |E| - |V| +1 cycles in the fundamental set of cycles with respect to any spanning tree of G . [RND77] FIGURE

set of fundamental cutsets A set of cutsets represented by the rows of a fundamental cutset matrix Qf.. [WM72] FIGURE

set packing problem Given a family of sets Si , 1 ≤ j≤ n , determine whether the family contains l mutually dist sets. [RND77] Shannon switching game A game played by the Spanner and the Cutter, one seeking to seize a set of elements spanning a specified element, the other seeking to prevent this. [DW96] shift graph Graph on the 2-subsets of [n] having {i, j} adjacent to {j, k} when i < j < k . [DW96] shortest path In a graph or network, this is a path from one node to another whose total cost is the least among all such paths. The "cost" is usually the sum of the arc costs, but it could be another function (e.g., the product for a reliability problem, or max for a fuzzy measure of risk). There are some particular labeling algorithms given. [HG99] shortest path algorithm The shortest path algorithm is a method for finding the shortest route from one vertex to another in a weighted graph. [DMP00] shortest path problem The problem of finding the shortest path from one vertex in a graph to another vertex. "Shortest" may be least number of edges, least total weight, etc. [PEB00] Given a graph G = (V, E) , length l(e) ∈Z+ for each e ∈ E , specified vertices a, b ∈ V , positive integer B . Is there a simple path from a to b in G having total length B or less? [GJ79] shortest path with forbidden pairs INSTANCE: Graph G = (V, E) , a collection C = {(a1, b1), … , (am, bm)} of pairs of vertices from V , an initial vertex s ∈V , and a final vertex f ∈V . SOLUTION: A simple path from s to f in G that contains at most one vertex from each pair in C. MEASURE: Length of the path, i.e., the number of edges in the path. [CK00] shortest total path length spanning tree problem

Given a graph G = (V, E) and integer bound B∈Z+, is there a spanning tree T for G such that the sum over all pairs of vertices u, v ∈V of the length of the path in T from u to v is no more than B ? [GJ79] shortest weight-constrained path INSTANCE: Graph G = (V, E) , length function l : E → N , weight function w : E →N , specified vertices s , t ∈V , and integer W . SOLUTION: A simple path in G with total weight at most W, i.e., a sequence of distinct vertices s = v1 , v2 , … , vm = t such that, for any 1 ≤ i ≤ m–1 , (vi , vi+1) ∈Eand Σ i=1m1w(vi , vi+1) ≤ W . MEASURE: The length of the path Σ i=1m1l(vi , vi+1) . [CK00] shortest weight-constrained path problem Given a graph G = (V, E) , lenght l(e) ∈Z+and weight w(e) ∈Z+ for each e ∈E , specified vertices s, t ∈V and positive integers K and W , is there a simple path in G from s to t with total weigth W or less and total length K or less? [GJ79] shorting an edge Deleting edge e and coinciding two vertices, which are the endpoints of edge e, to make one vertex. [WM72] sibling Two nodes connected to the same node which are same distance from the root in a rooted tree are called siblings. [EW00] sieve A combinatorial programming technique that takes a finite set and eliminates all the of that set that are not of interest. [RND77] signal flow graph A weighted oriented graph in which there are weights on both edges and vertices. [WM72] signature = g sign-biased graph = additively biased graph signed and biased graph = biased signed graph A graph separately signed and biased. [TZ98] signed digraph = sigraph Special case of weighted digraph, asg + or – to each edge. [DW96] FIGURE

signed gain graph = signed graph with gains A graph separately gained and signed. [TZ98]

signed graph Special case of weighted graph, asg + or – to each edge. [DW96] FIGURE

signed graph with gains = signed gain graph g = signature A sign labelling of the edges (except half and loose edges). [TZ98] FIGURE

sigraph = signed digraph simple graph (matroid) For a graph, having no loops or multiple edges. For a matroid, having no loops or parallel elements. [DW96] simple chain An edge sequence in which the vertices are distinct. [CGM79] A path in a graph in which all edges are distinct. FIGURE

simple circuit = simple cycle simple cycle = simple circuit A closed edge sequence with v0 = vn as the only nondistinct vertex. [CGM79] For a graph G = (V, E) a simple circuit is a sequence of distinct vertices from V such that {vi , vi+1} ∈E for 1 ≤ i ≤ k and such that {vk , v1} ∈E . [GJ79] FIGURE

simple digraph = simple directed graph A digraph with no loops or multiple arcs. [BW97] FIGURE

simple directed graph = simple digraph simple graph A graph with multiple edges and loops excluded. [BW97] A (usually finite) set of vertices V and set E of unordered pairs of distinct elements of V called edges. [CC99] A graph for which at most one edge connects any two nodes. Unless stated otherwise, the unqualified term "graph" usually refers to a simple graph. A non-simple graph with no loops but which can contain more than one edge between any two points is called a multigraph. [EW00] FIGURE

simple path

A path which repeats no vertex. [PEB00] A path which does not traverse any arc more than once. [BC79] A sequence of adjacent edges (v1, v2), (v2, v3), … , (vk-2, vk-1), (v k-1 , v k), in which all the vertices v1 , v2 , … , vk are distinct except possibly v1 = vk . [RND77] FIGURE

simplicial vertex A vertex x of G whose adjacency set induces a complete subgraph of G . [MG80] single-destination shortest-path problem Find the shortest path from each vertex in a weighted, directed graph to a specific destination vertex. Equivalent to the single-source shortest-path problem with all directions reversed. [PEB00] single-source shortest-path problem Find the shortest paths from a specific source vertex to every other vertex in a weighted, directed graph. Dijkstra's algorithm solves this if all weights are nonnegative. The BellmanFord algorithm handles any weights. [PEB00] sink A vertex, or node, in a directed graph which has no outgoing edges, more formally, one with out-degree 0. [PEB00]  In a directed graph, a vertex with outdegree 0.  In a flow graph, a vertex that may have a net flow into the vertex. In this case, the outdegree of the vertex may exceed 0. [HC00] FIGURE

site percolation A percolation which considers the lattice vertices as the relevant entities. [EW00] six-color theorem To color any map on the sphere or the plane requires at most six colors. This number can easily be reduced to five, and the four-color theorem demonstrates that the necessary number is, in fact, four. [EW00] size The number of edges, sometimes used for the number of vertices. [DW96] skd-tree = spatial kd-tree The spatial k-d tree is a spatial access method where successive levels are split along different dimensions. Objects are indexed by their centroid, and the minimum bounding box of objects in a node are stored in the node. [PEB00] skeleton = spanning forest

A set consisting of a spanning tree for each component of a disconnected graph. [RND77] FIGURE

skew partition A partition X, Y of V(G) such that G[X] and G[Y] are disconnected. [DW96] skew symmetry The property that the flow is the same amount, but reversed direction, starting from either vertex of every edge of a flow network. More formally, for an edge e = (v,w) , f (v,w) = - f (w,v) , where f (a,b) is the flow from a to b . [PEB00] Smith's network theorem In a network with three edges at each vertex, the number of Hamiltonian circuits through a specified edge is 0 or even. [EW00] snake A simple circuit in the d-hypercube which has no chords (i.e., for which all snake edges are edges of the hypercube). [EW00] snark A cubic graph of class two whose girth is at least 5. [CL96] solution An answer, a best possible situation or structure to found for a problem. [MG80] solvable problem A computational problem that can be solved by a Turing machine. The problem may have a nonbinary output. [PEB00] son = offspring source A vertex, or node, in a directed graph which has no incoming edges, more formally, one with in-degree 0. [PEB00]  In a directed graph, a vertex with indegree 0.  In a flow graph, a vertex which may have a net flow out of the vertex. In this case, the indegree of the vertex may exceed 0.  In a network, any of a set of vertices designated as sources. [HC00] FIGURE

source/sink cut A partition of the vertices of a network into sets S, T such that S contains the source and T contains the sink. [DW96]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so |

sp-sz | t | u | v | w | xyz |

| spectrum | square | state | strongly | sub | suffix | super | system | span function The span of a set X in a hereditary system consists of X and the elements not in X that complete circuits with subsets of X . [DW96] spanner = spanning subgraph spanning cycle A cycle in a graph that contains all the vertices of the graph. [ISEM00] spanning cycle ')"FIGURE

spanning forest = skeleton spanning graph A spanning graph for G = (V, E) is a subgraph G' = (V', E') such that V' = V . [SW87] spanning graph ')"FIGURE

spanning set A set whose span (in a hereditary system on E) is E . [DW96] spanning subgraph = spanner A subgraph H of G where V(H) = V(G) . [BW97] spanning subgraph ')"FIGURE

spanning tree A connected, acyclic subgraph containing all the vertices of a graph. [PEB00] A connected spanning subgraph containing no cycles. [BW97] A tree that includes all vertices of the graph. [CGM79]

A subset of n – 1 edges which form a tree. [EW00] A spanning subgraph for G which is a tree. [SW87] spanning tree ')"FIGURE

spanning tree parity problem Given a graph G = (V, E) and a partition of E into dist 2-element sets E1 , E2 , … , Em , is there a spanning tree T = (V, E ' ) for G such that for each Em , 1 ≤ i ≤ m , either Ei⊆E ' or Ei ∩E ' = 0 ? [GJ79] sparse graph A graph in which the number of edges is much less than the possible number of edges, that is, the number of vertices squared. [PEB00] sparse graph ')"FIGURE

sparsification Technique for deg dynamic graph algorithms, which when applicable transform a time bound of T(n,m) onto O(T(n,n)) , where m is the number of edges and n is the number of vertices of the given graph. [PEB00] sparsity The fraction of zeroes in a matrix. If A is m by n , and A(i, j) ≠ 0 for k of its elements, its sparsity is k / mn . Large linear programs tend to be very sparse, increasing as the dimensions get large. For example, consider the standard transportation problem with s sources and d destinations. This has m = (s + d) constraints and n = sd variables. Each column, however, has exactly 2 nonzeroes since A is the incidence matrix of the network, so its sparsity is 2n / mn, or simply 2/m , which decreases as the number of sources and/or destinations grows large. The sparsity of a simple graph (or network) is the sparsity of its adjacency matrix. More generally, the sparsity of a multigraph refers to the average degree of its nodes. [HG99] spatial kd-tree = skd-tree spectral graph partitioning A graphical partitioning based on the eigenvalues and eigenvectors of the Laplacian matrix of a graph. [EW00] spectrum = graph spectrum The set of graph eigenvalues. [EW00] spectrum of a signed graph

The spectrum S(G*) of a signed graph G* is the set of k elements such that G* has a signed embedding in the sphere with k crosscaps. [DA00] SPGC = strong perfect graph conjecture sphericity Minimum dimension in which G is the intersection graph of spheres. [DW96] splay tree A binary search tree in which operations that access nodes restructure the tree. [PEB00] A self-organizing data structure which uses rotations to move any accessed key to the root. This leaves recently accessed nodes near the top of the tree, making them very quickly searchable. [EW00] split graph An undirected graph G = (V, E) which has a partition V = S + K of its vertex set V into a stable set S and a complete set K. [MG80] A graph whose vertices can be covered by a clique and an independent set. [DW96] splittance The minimum number of edges to be added to an arbitrary undirected graph or erased from it to produce a split graph. [MG80] splitting tree A spanning tree T of a connected graph G is a splitting tree if at most one component of G – E(T) has odd size. [CL96] spread A tree having an infinite number of branches and whose nodes are sequences generated by a set of rules. [EW00] square graph The cycle graph C4 . [EW00] square graph ')"FIGURE

square of a graph The second power. [DW96] squashed cube dimension

Minimum length of the vectors in a squashed cube embedding. [DW96] squashed cube embedding Encodes vertices by 0, 1 *-vectors such that distance between two vertices is the number of coordinates where one has 0 and the other has 1. [DW96] s-t cut A partitioning of the vertices of a flow network into S and T such that the source is in S and the sink is in T . [PEB00] stability number = independence number stable set = independent set stable vertex set = independent set stack tree A binary tree where no node, except the root, has more than one non-leaf child. Note: This topology is used to define simple, fault-tolerant, acyclic networks. [PEB00] stacker crane problem Given a mixed graph G = (V, A, E) , length l(e) ∈Z0+for each e ∈A ∪E and bound B ∈Z+ , is there a cycle in G that includes each directed edge in A at least once, traversing such edges only in the specified directions, and that has total length no more than B ? [GJ79] star = star graph The tree with at most one non-leaf , K1, n-1 . [DW96] The n-star graph is a tree on n +1 nodes with one node having valency n and the others having valency 1. [EW00] star ')"FIGURE

star graph = star star-cutset Vertex cut inducing a subgraph containing a dominating vertex. [DW96] star-cutset lemma No p-critical graph has a star-cutset. [DW96] start vertex The first endpoint of a directed edge. [SE79]

state transition diagram = STD A diagram consisting of circles to represent states and directed line segments to represent transitions between the states. One or more actions may be associated with each transition. The diagram represents a Finite State Machine. [CERN97] state transition diagram ')"FIGURE

static device characteristic A collection of ordered pairs (v, i) where v, i are vectors on the set of edges E . [HN97] static graph The gain graph of a periodic graph. [TZ98] static network A network with static device characteristic. [HN97] STD = state transition diagram Steiner minimum tree Given a set of vertices S in an undirected weighted graph, a minimal weight spanning tree of S ∪ Q for some added Steiner vertices Q in the graph. [PEB00] Steiner point A point that is not part of the input set of points, for instance, a point computed to construct a Steiner tree. A point with a particular geometric relation to a triangle. [PEB00] Steiner problem Find a subgraph of a graph, say G' = [V',E'] , such that V' contains V* (a specified subset of nodes), and Sum{c(e): e∈E'} is minimized. It is generally assumed c≥ 0 . When |V*| = 2 , this is the shortest path problem. When |V*| = |V|, this is the (minimum) spanning tree problem. [HG99] Steiner ratio For a given variant of the Steiner tree problem, the maximum possible ratio of the length of a minimum spanning tree of a set of terminals to the length of an optimal Steiner tree of the same set of terminals. [PEB00] Steiner tree The Steiner tree of some subset of the vertices of a graph G is a minimum-weight connected subgraph of G that includes all the vertices. It is always a tree. Steiner trees have practical applications, for example, in the determination of the shortest total length of wires needed to some number of points. [EW00]

A minimum-weight tree connecting a designated set of vertices, called terminals, in a weighted graph or points in a space. The tree may include non-terminals, which are called Steiner vertices or Steiner points. [PEB00] Steiner tree ')"FIGURE

Steiner tree problem Given a graph G = (V, E) , weight w(e) ∈Z0+for each e ∈E , a subset R⊆Vand a positive integer bound B , is there a subtree of G that includes all the vertices of R and such that the sum of the weights of the edges in the subtrees is no more than B ? [GJ79] Steiner triple system = STS A K3-decomposable complete graph. [CL96] A Steiner triple system (STS) is a collection of points and triples of these points such that every pair occurs in exactly one triple. [DA00] Steiner's segment problem Given n points, find the line segments with the shortest possible total length which connect the points. The segments need not necessarily be straight from one point to another. [EW00] Steinitz's theorem A graph G is the edge graph of a polyhedron iff G is a simple planar graph which is 3connected. [EW00] 3-connected planar graphs have onely one embedding in the plane (more precisely, onely one dual graph). [DW96] Stern-Brocot tree A special type of binary tree obtained by starting with the fractions 0/1 and 1/0 and iteratively inserting (m + m') / (n + n') between each two adjacent fractions m / m' and n / n' . [EW00] Stern-Brocot tree ')"FIGURE

stochastic algorithm A stochastic algorithm is one whose algorithm map is a random variable. Unlike the meaning in computer science, most people in mathematical programming mean an algorithm whereby an iterate is selected by some random mechanism. One example is simulated annealing. When xk is a random variable, there is a meaning to convergence that differs from ordinary (deterministic) sequences. [HG99]

straight-line drawing A graph drawing in which each edge is represented by a straight line segment. [PEB00] straight-line drawing ')"FIGURE

strength Of a theorem, the fraction of the time when the conclusion holds that the hypotheses also holds. [DW96] strict digraph Digraph with at most one copy of each ordered pair, and no loops. [DW96] strict digraph ')"FIGURE

strictly balanced Average vertex degree is strictly greater than average vertex degree of any subgraph. [DW96] strictly connected graph A digraph in which for every two distinct vertices a and b there is either a path from a to b or a path from b to a . strictly connected graph ')"FIGURE

strictly parallel arcs Parallel arcs having the same orientation. [CGM79] strong component Maximal strongly connected subdigraph. [DW96] strong connectivity augmentation problem Given a digraph G = (V, A) , weight w(u, v) ∈Z+ for each ordered pair (u, v) ∈V× V and positive integer B , is there a set A ' of ordered pairs of vertices from V such that Σ a ∈ A ' w(a) ≤ B and such that the graph G ' = (V, A ∪A ' ) is strongly connected ? [GJ79] strong digraph A digraph D is strong if for every pair u, v of vertices of D, there is both a u-v path and a vu path. [CL96] strong digraph ')"FIGURE

strong orientation

Orientation of G in which each vertex is reachable from every other. [DW96] strong orientation ')"FIGURE

strong perfect graph conjecture = SPGC The conjecture that a graph is perfect if and only if it has no odd hole or odd antihole. [DW96]

The conjecture that a graph is perfect iff neither the graph nor its complement contains an odd cycle of length at least five as an induced subgraph. [EW00] strong product A graph product with vertex set V(G1) × V(G2) and edge set (u1 , v1) ↔ (u2 , v2) if u1 = u2 or u1↔ u2 and v1 = v2 or v1 ↔v2 . [DW96] strongly connected component = dicomponent A maximal subgraph of a directed graph such that for every pair of vertices u , v in the subgraph, there is a directed path from u to v and a directed path from v to u . [EW00] The maximal strongly connected subgraph. [RND77] strongly connected digraph Digraph with each vertex reachable from all others. [DW96] strongly connected digraph ')"FIGURE

strongly directed circuit The set of edges of a strongly directed circuit graph. [HN97] strongly directed circuit ')"FIGURE

strongly directed circuit graph A graph in which the edges are arranged in a sequence so that the negative endpoint of each edge is the positive endpoint of the succeeding edge and the positive endpoint of the last edge is the negative endpoint of the first. [HN97] strongly directed circuit graph ')"FIGURE

strongly directed crossing edge set A crossing edge set in which the positive endpoints of all its edges are in the same end

vertex set. [HN97] strongly directed path A path in which the edges can be arranged in a sequence so that the negative endpoint of each edge except the last is the positive endpont of the succeeding edge. [HN97] strongly directed path ')"FIGURE

strongly perfect graph A graph in which some stable set meets every maximal clique. [DW96] strongly regular graph A k-regular graph whose adjacent pairs have λ common neighbors, and whose nonadjacent pairs have µ common neighbors. [DW96] structural balance Balance of a signed graph associated to a social structure like a small social group, a kinship or marriage system, etc. [TZ98] structural Ramsey theory A generalization of Ramsey theory to mathematical objects in which one would not normally expect structure to be found. [EW00] STS = Steiner triple system subconstituent The subgraph induced by a vertex neighborhood or by a vertex nonneighborhood. [DW96] subcontraction = minor subdigraph A subgraph of a directed graph. [DW96] subdigraph ')"FIGURE

subdivision The operation of replacing an edge by a 2-edge path through a new vertex. [DW96] subdivision graph A graph obtained by a sequences of subdivisions. [DW96] subeulerian graph A graph G is called subeulerian if it is possible to add edges to G to obtain an Eulerian

graph. [CL96] subgraph A subgraph of a graph G = (V(G), E(G)) is a graph H = (V(H), E(H)) such that V(H) ⊆ V(G) and E(H) ⊆ E(G) . [BW97] A graph whose vertices and edges all belong to G . [DW96] A subset T1 ⊂ T of the vertex set T of a given graph G = G(T, S) together with maximal subset S1 = {(a, b) : (a, b) ∈ S and a, b ∈ T1} of the edge set S . subgraph ')"FIGURE

subgraph homeomorphism problem Given a graph G = (V, E) , does G contain a subgraph homeomorphic to H ? [GJ79] subgraph isomorphism problem Decide if there is a subgraph of one graph which is isomorphic to another graph. [PEB00] Given two graphs G1 = (V1 , E1) and G2 = (V2 , E2) , does G1 contain a subgraph isomorphic to G2 ? [GJ79] submodular function Let N be a finite set and let f be a function on the subsets of N into R . Then, f is submodular if it satisfies: f(S∪T) ≤ f(S) + f(T) - f(S ∩T) for S , T ⊆ N . [HG99] submodularity property The property of having a submodular rank function. [DW96] subset The set B is said to be subset of A , B ⊆A , if every element of B is an element of A . [BC79] subtraction of graphs G1 − G2 : a subgraph of G1 obtained by deleting all edges which are also in G2 . [WM72] subtree A tree T ' whose vertices and edges form subsets of the vertices and edges of a given tree T

. [EW00] subtree representation Assigns subtrees of a host tree to each vertex of a chordal graph so that vertices are adjacent if and only if the corresponding subtrees intersect. [DW96] successor For u in a digraph, a vertex v with u →v . [DW96] suffix tree A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents. [PEB00] sum For cycles and cocycles, taken modulo 2. For a graph, the dist union. For matroids on dist sets, the matroid on their union whose independent sets are all unions of an independent set from each. [DW96] supbase A set of elements containing a base. [DW96] supereulerian A graph G is called supereulerian if it is possible to remove edges from G to obtain an Eulerian graph. [CL96] supergraph If G' is a subgraph of G , then G is said to be a supergraph of G' . [EW00] supermodular function Let S be a finite set. Let f : 2S →R , f is said to be a supermodular function if f(X) + f(Y) ≤ f(X ∪ Y) + f(X ∩ Y)∀X , Y⊆S . [HN97] Negative of the submodular function. [HG99] superregular graph A regular graph that is null or whose subconstituents are all superregular. [DW96] supersink A vertex, or node, in a directed graph which is reachable from all other vertices. [PEB00] supersource A vertex, or node, in a directed graph from which all other vertices are reachable. [PEB00]

supply Source constraint in a transportation network. [DW96] surface A compact orientable 2-manifold. [CL96] sweep subgraph The curbs available for sweeping in the streetsweeper problem. [DW96] switched bond graph Bond graph extended with an ideal switch element. [PM99] switching class = Seidel switching class An equivalence class of simple graphs under Seidel switching. [TZ98] switching equivalence The relation between two simple graphs that one is obtained from the other by Seidel switching. [TZ98] symmetric For a graph, having a non-trivial automorphism. For a digraph, having u → v if and only if v → u . For a binary relation, having xRy if and only if yRx . [DW96] symmetric binary B-tree = red-black tree symmetric difference An operation between the sets A and B such that A ⊕ B = {x| x∈ (A ∪ B) , x ∉ (A ∩B)} . [RND77] The set of elements in exactly one of A and B . [DW96] symmetric digraph A digraph is called symmetric if, whenever (u, v) is an arc of D , then (v, u) is also an arc of D . [CL96] symmetric traveling salesman problem The problem of finding a minimum-cost Hamiltonian cycle in a weighted undirected graph. [RND77] system of distinct representatives = SDR = transversal Szekeres-Wilf theorem

χ (G) ≤ 1 + max H ⊆ G δ (H) . [DW96]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so | sp-sz |

t | u | v | w | xyz |

| terminal | thickness | time | topology | tournament | transformable | transversal | triangulation | two | tabu search This is a meta-heuristic to solve global optimization problems, notably combinatorial optimization, based on multi-level memory management and response exploration. It requires the concept of a neighborhood for a trial solution (perhaps partial). [HG99] tail = positive endpoint The first vertex of an edge in a digraph. [DW96] Tait coloring A 3-coloring of graph edges so that no two edges of the same color meet at a vertex. [EW00] For a planar cubic graph, a proper 3-edge-coloring. [DW96] FIGURE

Tait cycle A set of circuits going along the edges of a graph, each with an even number of edges, such that just one of the circuits es through each vertex. [EW00] FIGURE

Tait's Hamiltonian graph conjecture Every 3-connected cubic graph has a Hamiltonian circuit. Proposed by Tait in 1880 and refuted by Tutte (1946) with the counterexample now known as Tutte's graph. Had the conjecture been true, it would have implied the four-color theorem. [EW00] Tarry's algorithm Procedure for exploring a maze. [DW96] technique A specific method of performing an operation. The algorithm, method, and procedure are also used interchangeably. [EW00] telegraph problem Directed version of gossip problem with one-way transmissions. [DW96] Tellegen's theorem Any voltage vector of G is orthogonal to every current vector of G . [HN97]

terminal The set of points in a plane or vertices in a graph defining endpoints of a Steiner tree. [PEB00] terminal edge A cut edge incident with a leaf. [DW96] FIGURE

terminal endpoint The node xj of an arc (xi , xj) . [BC79] terminal node = leaf terminal vertex = leaf terminal vertices Two vertices of odd degree in a M-graph. [WM72] ternary matroid Representable over the field with three elements. [DW96] ternary tree = 3-ary tree A tree in which each of its vertices has outdegree 3 or less. [SW87] FIGURE

tetragon A polygon having four sides or angles; a quadilateral or quadrangle.[HC00] FIGURE

tetrahedral graph The unique polyhedral graph on four nodes which is also the complete graph K4. The tetrahedral graph has 4 nodes, 6 edges, vertex connectivity 4, edge connectivity 3, graph diameter 1, graph radius 1, and girth 3. [EW00] FIGURE

theta graph = handcuff = bicycle thickness = edge thickness = graph thickness The minimum number of planar graphs whose union is G . [BW97] The minimum number of pairwise edge-dist planar spanning subgraphs of G whose edge sets is a partition of E(G) . [CL96] Thomsen graph = utility graph thrackle A graph formed by a collection of curves in the plane, with the property that the curves corresponding to any pair of edges meet in a single point, which is either an endpoint of both

edges or a place where the two curves cross. Every planar straight line graph thrackle has at most as many edges as vertices; Conway's thrackle conjecture states that this is true even for curved thrackles. [ODC00] A thrackle is a drawing of a graph such that every pair of nonadjacent edges cross. The name is coined by John Conway, who notes that a thrackle is also a tangle of fishing line. [DA00] thrackle conjecture If a graph can be thrackled, then its number of edges is not greater than its number of vertices. [DA00] threaded tree A binary search tree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-order successor. [PEB00] threshold dimension Minimum number of threshold graphs whose union is G . [DW96] threshold function A function t of n such that some property almost always or almost never occurs, depending on whether a particular parameter belongs to o(t) or to ω (t) . [DW96] threshold graph Having a threshold t and a vertex weighting ω such that u / ↔ v if and only if w(u) + w(v) ≤ t . Many other characterizations, including absence of a 2-switch and existence of a construction ordering by adding isolated or dominating vertices. [DW96] threshold number problem Given a graph G = (V, E) and positive integer K ≤ | E | , is there a partition of E into dist sets E1 , E2 , … , Eksuch that each of the graphs Gi = (V, Ei) ,1 ≤ i≤ K , is a threshold graph? [GJ79] time complexity function The function that expresses for an algorithm its time requirements by giving , for each possible input length, the largest amount of time needed by the algorithm to solve a problem instance of that size. [GJ79] timetable problem Given a set of hours in the week, a collection of n teachers, each of whom is available to teach during some subset of the set of hours, a set of m classes, each of which can be scheduled only during certain hours of the week, and an n × m matrix of nonnegative integers in which the ijth element is the number of hours the i-th teacher must teach the j-th class. Determine if it is possible to assign meeting times and teachers to the classes so that every class meets during the

required hours, every teacher can be at his classes, there is only one teacher per class, and no teacher has two classes simultaneously. [RND77] to cover A graph G covers a graph H if there exists a graph map f from G to H such that the edges incident with a vertex v map bijectively to those incident with u = f(v) . [DA00] to dominate A vertex v in a graph G is said to dominate itself and each of its neighbors. [CL96] topological degree of freedom = hybrid rank The minimum size of the set of node voltages and branch currents in an electrical network from which, by using Kirchhoff's equations, we can find either the voltage or the current associated with each branch. [HN97] topological graph A simple unlabeled graph whose connectivity is considered purely on the basis of topological equivalence, so that two edges (v1, v2) and (v2, v3) ed by a node v2 of degree two are considered equivalent to the single edge (v1, v3) .[EW00] topological graph theory The study of drawings of graphs on surfaces. [DW96] topological ordering A labelling of the vertices with consecutive integers so that every arc is directed from a smaller label to a larger label. [WC00] topological sort This sorts the nodes in a network such that each arc, say k-th, has Tail(k) < Head(k) in the renumbered node indexes. This arises in a variety of combinatorial optimization problems, such as those with precedence constraints. If the nodes cannot be topologically sorted, the network does not represent a partially ordered set. This means, for example, there is an inconsistency in the constraints, such as jobs that cannot be sequenced to satisfy the asserted precedence relations. [HG99] A topological sort is a permutation p of the vertices of a graph such that an edge {i , j} implies that i appears before j in p . Only directed acyclic graphs can be topologically sorted. [EW00] topology digraph An unlabeled transitive digraph with n nodes. [EW00] topology tree = series-reduced tree Tree that describes a balanced decomposition of another tree, according to its topology. [PEB00] A tree in which all nodes have degree other than 2 (in other words, no node merely allows a

single edge to " through"). [EW00] toroidal  For a graph, having a 2-cell embedding on the torus.  For a topological parameter, the version using the torus in place of the plane (toroidal thickness, crossing number etc.). [DW96] torus The (orientable) surface with one handle. [DW96] total chromatic number The smallest number of colors needed to color the vertices and edges of G so that adjacent vertices, adjacent edges, and incident vertices and edges are colored differently. [BW97] The minimum k for which a graph G its a k-total coloring. [CL96] total coloring An assignment of colors to the elements (vertices and edges) of G so that adjacent elements and incident elements of G are colored differently. [CL96] A labeling of both the vertices and edges. [DW96] FIGURE

total coloring conjecture Every graph G has a proper total coloring using at most ∆ (G) + 2 colors. [DW96] total domination number Minimum number of vertices in a set S such that every vertex has a neighbor in S . [DW96] total graph The total graph T(G) of a graph G has a vertex for each edge and vertex of G, and edge in T(G) for every edge-edge and vertex-edge adjacency in G . Total graphs are generalizations of line graphs. [EW00] The intersection graph of the sets in V(G) ∪E(G) for some G . [DW96] total interval number Minimum of the total number of intervals used to represent G as the intersection graph of unions of intervals on the real line. [DW96] totally cyclic orientation An orientation in which every edge belongs to a bidirected cycle. [TZ98] totally unimodular A matrix in which all square submatrices have determinant 0 or ± 1 . [DW96] toughness

The minimum t such that | S | ≥ tc(G – S) , where S is any vertex cut and c(G – S) is the number of components of the subgraph obtained by deleting S . [DW96] tournament A complete directed graph. The term "tournament" also refers to an arrangement by which teams or players play against certain other teams or players in order to determine who is the best. [EW00] A directed graph in which any two vertices are ed by exactly one arc. Such graphs can be used to record the results of games in which draws are not allowed. Each team is represented by a vertex, and the arc ing any two given teams is directed toward the loser; the number of wins for a particular team is the out-degree of the vertex representing the team. A tournament cannot contain more than one source or sink. [HC00] FIGURE

tournament matrix A matrix for a round-robin tournament involving n players competing in n (n - 1) / 2 matches (no ties allowed) having entries aij= 1 if player i defeats player j , aij= -1 if player i loses to player j , and aij = 0 if i = j . [EW00] tower of Hanoi problem There are three poles labeled A, B, C . On pole A , n discs of radius 1, 2, … , n (each with a hole in the middle) are piled up in such a way that the disc of radius i is the i-th from the top. The problem is to move all n discs to pole C so that again the disc i is the i-th from the top. Only one disc may be moved at a time, from any pole to any other one, subject to the restriction that no disc may ever rest above a smaller disc on the same pole. [RND77] FIGURE

trace Sum of the diagonal elements of a matrix. [DW96] traceable graph A graph G is traceable if it has a path that includes every vertex of G . [BW97] Having a Hamiltonian path. [DW96] FIGURE

tractable problem A problem which has an algorithm which computes all instances of it in polynomial time. [PEB00] trail A walk with all edges distinct. [BW97] A trail is a walk that allows repeated vertices but not edges. [TZ98] FIGURE

transformable problem = reducible problem

A problem P1 is transformable to a problem P2 if any instance of P1 can be transformed in polynomial time into an instance of P2 , such that the solution of P1 can be obtained in polynomial time from the solution to the instance of P2 . [RND77] transitive automorhism group An automorphism group that contains automorphisms mapping each vertex of G to every other vertex. [BW97] transitive closure The transitive closure of a digraph G(E, V) is a digraph G'(E, V) such that there is an edge u →v in G' if and only if there is a (non-empty) directed path from u to v in G . [SE79]  For a digraph D, the digraph with u →w whenever there is a path from u to w in D .  For a relation R , the relation S with xSy whenever there is a sequence x0 , …, xk with x = x0Rx1R … Rxk = y . [DW96]  FIGURE transitive digraph A graph G is transitive if any three vertices (x, y, z) such that edges (x, y), (y, z) ∈G imply (x, z) ∈G . Unlabeled transitive digraphs are called topologies. [EW00] transitive graph A graph G is called n-transitive with n ≥ 1 if it has an n-route and if there is always a graph automorphism of G sending each n-route onto any other n-route. [EW00] transitive reduction The transitive reduction of a directed graph G is the directed graph G' with the smallest number of edges such for every path between vertices in G, G' has a path between those vertices. Informally G' is the minimal graph with the connectivity as G . [PEB00] transitive reduction problem Given a digraph G = (V, A) and positive integer K , is there an A' ⊆ V × V with | A' | ≤ K such that for all u, v ∈ V the graph G' = (V, A') contains a path from u to v if and only if G does ? [GJ79] transitive subgraph problem Given a digraph G = (V, A) and positive integer K ≤ | A | , is there a subset A ' ⊆ A with | A ' | ≥ K such that G ' = (V, A ' ) is transitive? [GJ79] transitive tournament A tournament T is transitive if whenever (u, v) and (v, w) are arcs of T , then (u, w) is also an arc of T . [CL96] transitive triple The 3-node tournament. [EW00]

FIGURE

transitively orientable graph = comparability graph transportation constraints Supplies and demands. [DW96] transportation problem Find a flow of least cost that ships from supply sources to consumer destinations. This is a bipartite network, N = [S*T, A] , where S is the set of sources, T is the set of destinations, and A is the set of arcs. In the standard form, N is bi-complete (A contains all arcs from S to T), but in practice networks tend to be sparsely linked. Let c(i, j) be the unit cost of flow from i in S to j in T, s(i) = supply at i-th source, and d(j) = demand at j-th destination. Then, the problem is the linear program: Minimize Sum ij{c(i, j) x(i, j): i∈ S, j ∈T}: x≥ 0, Sum j{x(i, j): j ∈T} ≤ s(i) for all i∈S ; Sum i{x(i, j): i ∈S} ≥ d(j) for all j∈T . The decision variables (x) are called flows, and the two classes of constraints are called supply limits and demand requirements, resp. (Some authors use equality constraints, rather than than the inequalities shown.) An extension is the capacitated transportation problem, where the flows have bounds: x ≤ U .[HG99] Generalization of the assignment problem with supplies at each source and demands at each destination. [DW96] transposition graph A graph in which nodes correspond to permutations and edges are placed between permutations that differ by exactly one transposition. All cycles in transposition graphs are of even length, making them bipartite. [EW00] FIGURE

transshipment problem This is an extension of the transportation problem whereby the network is not bipartite. Additional nodes serve as transshipment points, rather than provide supply or final consumption. The network is N= [V, A] , where V is an arbitrary set of nodes, except that it contains a non-empty subset of supply nodes (where there is external supply) and a nonempty subset of demand nodes (where there is external demand). A is an arbitrary set of arcs, and there could also be capacity constraints. [HG99] transversal = system of distinct representatives = SDR From a collection of sets, a choice of one member from each set so that all the representatives are distinct. [DW96] Given a set S and a family of subsets A1 , A2 , ... , Ak of S, an assignment of k distinct elements s1 , s2 , ... , sk of S such that si is in Ai for all i . [ODC00] Ordered set (x1, x2, … , xn) of n elements composed from the representatives of the fixed sets

H1, H2, … , Hn where xk ∈ Hk for all k . transversal matroid A matroid whose elements are one partite set of a bipartite sets and whose independent sets are those that can be saturated by matchings. [DW96] traveling salesman polytope non-adjacency problem Given a graph G = (V, E) and two Hamiltonian circuits C and C ' for G , do C and C ' correspond to non-adjacent vertices of the traveling salesman polytope for G ? [GJ79] traveling salesman problem = TSP = traveling salesperson problem Given a finite set C = {c1 , c2 , … , cm} of cities, a distance d(ci , cj) ∈ Z+ for each pair of cities ci , cj ∈C, and a bound B ∈ Z+ (where Z+ denotes the positive integers), is there a tour of all cities in C having total length no more than B ?[GJ79] Find a path through a weighted graph which starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges. Less formally, find a path for a salesman to visit every listed city at the lowest total cost. [PEB00] A problem in graph theory requiring the most efficient (i.e., least total distance) Hamiltonian circuit a salesman can take through each of cities. No general method of solution is known, and the problem is NP-hard. [EW00] Find a shortest path through every fixed vertex exactly once given the distances between the vertices. FIGURE

traveling salesperson problem = TSP = traveling salesman problem treap A binary search tree in which nodes have another key, called the priority. Operations also keep nodes in heap order with regard to the priority. The name comes from "tree" and "heap". [PEB00] tree An acyclic connected graph. [CL96] A connected subgraph having nv(G) vertices and nv(G) – 1 edges. [WM72] An undirected graph where every pair of vertices of the graph is connected by exactly one chain. [CGM79] A forest of a connected graph. [HN97] A tree is a mathematical structure which can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph. Trees were first studied by Cayley

(1857). A tree graph is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). [EW00] A connected graph without cycles. FIGURE

tree ittance product The product of all ittances which are the weigths of edges in a tree.[WM72] tree branch = branch tree centroid The set of all centroid points in a weighted tree. [EW00] tree contraction Contracting a tree by removing some of the nodes. [PEB00] tree editing problem The problem of finding an edit script of minimum cost which transforms a given tree into another given tree. [PEB00] tree root Any vertex selected as a start vertex of the tree. FIGURE

tree traversal A technique for processing the nodes of a tree in some order. [PEB00] triangle A cycle of length 3. [BW97] A 3-cycle. [CL96] FIGURE

triangle graph The cycle graph C3 , which is also the complete graph K3. [EW00] FIGURE

triangle inequality The property that a complete weighted graph satisfies weight (u,v) ≤ weight (u,w) + weight (w,v) for all vertices u, v, w. Informally, the graph has no short cuts. [PEB00] d(x, y) + d(y, z) ≥ d( x, z) . [DW96] triangle-free Not having K3 as a subgraph. [DW96] FIGURE

triangle-free graph A graph with no cycles of length 3. [BW97] FIGURE

triangular chord Chord of length two along a path or cycle. [DW96] triangulated graph = chordal graph triangulation = maximal planar graph A graph where each face is bounded by a triangle. [BW97] A graph embedding on a surface such that every region is a 3-gon. [DW96] A planar graph having the property that no additional edges can be added so that the resulting graph is still planar. [HC00] triconnected graph A graph in which there are exactly three paths between any pair of distinct vertices. [PEB00] trie A digital search tree represented in a special way. [RND77] A tree for storing strings in which each edge is labeled by characters. Common prefixes are represented by tree branches, and the unique suffixes are stored at the leaves. [PEB00] tripartite graph In a tripartite graph, the vertices are partitioned into three sets (partitions) so that no two vertices contained in any one partition are adjacent. [ISEM00] trivalent Having degree 3. [DW96] trivalent graph = cubic graph trivial graph Graph with no edges (some authors restrict to one vertex). [DW96] FIGURE

trivial path A path of length 0. [TZ98] trivial trail A trail of length 0. [TZ98] trivial walk A walk of length 0. [TZ98] TSP = traveling salesman problem

Turan graph Complete equipartite graph. [DW96] The (n, k)-Turan graph is the extremal graph on n vertices which contains no k-clique. In other words, the Turan graph has the maximum possible number of edges of any n-vertex graph not containing a complete graph Kk. [EW00] FIGURE

Turan theorem Characterization of the complete r-partite graphs as the largest graphs of a given order with no (r+1)-clique. [DW96] Turan's brickyard problem The vertices in one partite set are the kilns in a brickyard; the vertices in the other partite set are the shipping depots. Each kiln is to be connected by a train track to each depot. However, when tracks cross the cars are likely to be derailed. Hence it is useful to find the layout of kilns, depots, and tracks that minimizes the number of crossings. [DA00] Tutte polynomial For a graph G , possibly containing loops and multiple edges, we define the Tutte polynomial T(G; x, y) by the following properties: T(G; x, y) = y T(G - e; x, y) if e is a loop, T(G; x, y) = x T(G.e; x, y) if e is a cut edge, T(G; x, y) = T(G - e; x, y) + T(G.e; x, y) otherwise, T(G; x, y) = 1 if G has no edges. [SL99] Tutte-Coxeter graph The 8-cage. [CL96] twig Let a cotree of a spanning tree T in a connected graph G be denoted T*. Then the edges of G which are not in T* are called its twigs. [EW00] FIGURE

twins Vertices having the same neighborhood (false twins are adjacent vertices with the same closed neighborhoods). [DW96] FIGURE

two-colorable graph = bipartite graph = bigraph two-graph A two-graph (V, ∆ ) is a graph on nodes V with a collection ∆ of unordered triples of the vertices (the so-called "odd triples") such that each 4-tuple of V contains an even number of elements of ∆ as subsets. [EW00] two-way infinite edge sequence A sequence of edges of an infinite graph of the form

. . . , v -1 v0 , v0 v1 , v1 v2 , . . . . [HC00]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so | sp-sz | t |

u | v | w | xyz |

| undirected | union | utility | u, v-path A path with u and v as endvertices. [DW96] u,v-walk A walk from u to v . [DW96] Ulam's conjecture Let graph G have p vertices vi and graph H have p vertices ui , where p ≥ 3 . Then if for each i , the subgraphs Gi = G – vi and Hi = H – ui are isomorphic, then the graphs G and H are isomorphic. [EW00] ultrametric tree An edge-weighted tree T(V, E) with n leaves such that, for any pair of leaves i and j , dijT≥ M [i, j] where dijTdenotes the sum of the weights in the path between i and j . [CK00] unavoidable set A collection of configurations such that every graph in a specified class contains some configuration in the collection. [DW96] unbalanced = frustrated unconnected subgraph problem Given a digraph G = (V, A) and positive integer K ≤ | A | , is there a subset A ' ⊆ A with | A ' | ≥ K such that G ' = (V, A ' ) has at most one directed path between any pair of vertices? [GJ79] uncountable graph A graph that is not countable. [HC00] underlying graph A graph obtained from the digraph D by replacing each arc (u, v) or symmetric pairs (u, v) and (v, u) by the edge uv . [CL96] underlying graph

')"FIGURE

undirected edge Edges in graphs are undirected (as opposed to those in digraphs). [CC99] undirected edge ')"FIGURE

undirected flow with lower bounds problem Given a graph G = (V, E) , specified vertices s and t , capacity c(e) ∈Z+ and lower bound l(e) ∈Z0+ for each e ∈E and a requirement R∈Z+ , is there a flow function f : {(u, v), (v, u) : {u, v} ∈E } →Z0+such that for all {u, v} ∈ E , either f ((u, v)) = 0 or f ((v, u)) = 0 , for each e = {u, v} ∈ E , l(e) ≤ max { f ((u, v)) , f ((v, u)) } ≤ c(e) , for each v ∈ V – {s, t} , flow is conserved at v , the net flow into t is at least R ? [GJ79] undirected graph = nonoriented graph A graph for which the relations between pairs of vertices are symmetric, so that each edge has no directional character (as opposed to a directed graph). Unless otherwise indicated by context, the term "graph" can usually be taken to mean "undirected graph". [EW00] A graph with undirected edges. undirected graph ')"FIGURE

undirected path A sequence of vertices in which either (ai , ai+1) or (ai+1 , ai) is an edge. [SW87] undirected path ')"FIGURE

undirected two-commodity integral flow problem Given a graph G = (V, E) , specified vertices s1, s2 , t1 and t2, capacity c(e) ∈Z+for each e∈E and requirements R1 , R2 ∈Z+, are there two flow functions f1 , f2 : {(u, v), (v, u) : {u, v} ∈E } →Z0+ such that for all {u, v} ∈ E and i∈ {1, 2} , either f i((u, v)) = 0 or fi((v, u)) = 0 , for each {u, v} ∈ E , max { f 1((u, v)), f 1((v, u))} + max { f 2((u, v)), f 2((v, u))} ≤ c({u, v}) , for each v ∈ V – {s, t} and i ∈ {1, 2} , flow fi is conserved at v , for i ∈ {1, 2} , the net flow into ti under flow fi is at least Ri ? [GJ79] unicursal circuit A circuit in which an entire graph is traversed in one route. An example of a curve which can be traced unicursally is the Mohammed sign.

[EW00] unicursal circuit ')"FIGURE

unicursal graph Connected graph in which it is possible to traverse all edges exactly once in a continuous manner. [CGM79] unicursal graph ')"FIGURE

unicyclic graph A connected graph containing exactly one cycle. [EW00] unicyclic graph ')"FIGURE

uniform matroid A matroid on [n] in which the independent sets are those of size at most k . [DW96] unilateral digraph A digraph D is unilateral if for every pair u, v of vertices of D, there is either a u-v path or a vupath. [CL96] unilateral digraph ')"FIGURE

unilateral surface A nonorientable two-dimensional manifold (e.g., the Möbius strip or Klein bottle) that has only one side. [HC00] unilateral surface ')"FIGURE

unimodular matrix For matrices, having determinant 0 , +1 , or –1 . [DW96] union of graphs = = graph union = graph The union G = G1 ∪ G2 of graphs G1 and G2 with dist vertex sets V1 and V2 and edge sets E1 and E2 is the graph with V = V1∪V2 and E = E1∪E2 . [EW00] A graph whose vertex set is the union of the vertices in G1and G2 and whose edge set is the union of the edges in G1 and G2 (written G1 + G2 if the vertex sets are dist). [DW96] union of graphs ')"FIGURE

union of matroids

The union of matroids M1, …, Mk is the hereditary system whose independent sets are {I1 ∪ … ∪Ik: Ii∈Ii} . [DW96] unit circular-arc graph A graph G is a unit circular-arc graph if there exists a circular-arc representation for G in which every arc is of unit length. [MG80] unit distance graph A distance graph in which all edges are of length 1. [EW00] The graph with vertex set ℜ 2 in which points are adjacent if the distance between them is 1. [DW96] unit neighborhood graph A distance graph with distance set [0, 1]. [EW00] unitransitive graph A graph G is n-unitransitive if it is connected, cubic, n-transitive, and if for any two n-routes W1 and W2 , there is exactly one automorphism α of G such that α W1 =W2 . [EW00] unitransitive graph ')"FIGURE

unlabeled graph A graph in which individual nodes have no distinct identifications except through their interconnectivity. Graphs in which labels (which are most commonly numbers) are assigned to nodes are called labeled graphs. Unless indicated otherwise by context, the unmodified term "graph" generally refers to an unlabeled graph. [EW00] unlabeled graph ')"FIGURE

unoriented incidence matrix The matrix whose rows are indexed by the vertices and whose columns are indexed by the edges and whose (v, e) entry equals the number of ends of e that are incident with v . [TZ98] unsolvable problem A computational problem that cannot be solved by a Turing machine. The associated function is called an uncomputable function. [PEB00] utility graph = Thomsen graph The utility problem posits three houses and three utility companies − say, gas, electric, and water − and asks if each utility can be connected to each house without having any of the gas/water/electric lines/pipes over any other. The problem was first posed in this form by H. E. Dudeney in 1917. The utility graph UG is the graph showing the relationships described

above. It is known in the more formal parlance of graph theory as the complete bipartite graph K3, 3 . [EW00] utility graph ')"FIGURE

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so | sp-sz | t | u |

v | w | xyz |

| vertex | vertex degree | vertex signed | voltage | valence = degree valency = vertex degree value of a flow The net flow out of the source or into the sink. [DW96] Vamos matroid A particular nonlinear matroid with eight elements. [DW96] VDU = vertex dist union vector space associated with a graph Let E be the power set of the edge set of a simple graph G ; i.e., the set of all subsets of the set of edges of G . If E and F are of E , define E + F to be the set of edges of G that lie in either E or F but not in both. Define scalar multiplication by elements of the field of integers modulo 2: (E) • 1 = E and (E) • 0 = Ø ÷ , the empty set. The vector space formed in this manner is known as the vector space associated with the graph G . [HC00] vehicle routing problem = VRP Find optimal delivery routes from one or more depots to a set of geographically scattered points (e.g., population centers). A simple case is finding a route for snow removal, garbage collection, or street sweeping (without complications, this is akin to a shortest path problem). In its most complex form, the VRP is a generalization of the TSP, as it can include additional time and capacity constraints, precedence constraints, plus more. [HG99] vertex = node A vertex is located at the end of an edge and is usually represented pictorially by a dot. [DMP00] An element of one of two (usually finite) sets of elements that determine a graph; i.e., an element of the vertex set. [HC00]

An end point of the edge of a graph or an isolated point in a graph. FIGURE

vertex arboricity The minimum number of subsets into which V(G) can be partitioned so that each subset induces an acyclic subgraph. [CL96] vertex basis A vertex basis of a digraph G = (V, E) is a minimal subset B ⊆ V with the property that there is a path of length zero or more to every vertex in V from some vertex in B . [RND77] vertex block = node block A maximal subgraph that is 2-connected and has at least one vertex. [TZ98] vertex chromatic number = chromatic index vertex coloring An vertex coloring of a graph refers to the choice and arrangement of colors for the vertices. Formally, a vertex coloring of a graph is a one-to-one function from the set of the graphs's vertices into the set of all colors. [ISEM00] FIGURE

vertex component = node component A maximal connected subgraph that has a vertex. A loose edge is not a vertex component, but an isolated vertex is. [TZ98] vertex connected component A set of all vertices which can be reached from the given vertex by elementary paths together with edges incident to these vertices. vertex connectivity = connectivity vertex cover = vertex covering A set of vertices containing at least one endpoint of every edge. [DW96] FIGURE

vertex cover problem Given a graph G = (V, E) and a positive integer K ≤ |V| , is there a vertex cover of size K or less for G ? [GJ79] vertex covering = vertex cover vertex covering number The minimum cardinality of a vertex cover in G . [CL96] vertex critical

Deletion of any vertex changes the parameter. [DW96] vertex cut = separating set of vertices A set S of vertices of a graph G such that G – S is not connected. [HC00] A set of vertices whose removal disconnects the graph. [BW97] FIGURE

vertex degree = local degree = valency = local vertex degree = vertex order The number of edges which touch the vertex. Directed graphs have two types of degrees, known as the indegree and outdegree. [EW00] FIGURE

vertex dist union = VDU A set of vertex subsets such that no two have vertices in common. [WM72] FIGURE

vertex frustration number = frustration number vertex induced subgraph A vertex-induced subgraph is one that consists of some of the vertices of the original graph and all of the edges that connect them in the original. [ISEM00] FIGURE

vertex multiplication A replacement of vertices of G by independent sets such that copies of x and y are adjacent if and only if xy ∈ E(G) . [DW96] vertex order = vertex degree vertex pancyclic graph A connected graph G of order n ≥ 3 is called vertex-pancyclic if for each vertex v of G and for every integer l satisfying 3 ≤ l ≤ n , there is a cycle of G of length l that contains v . [CL96] vertex partition A partition of the vertex set. [DW96] FIGURE

vertex set The set of elements on which the graph is defined. [DW96] vertex signed graph = marked graph Graph with signed vertices. [TZ98] FIGURE

vertex switching

Seidel switching of a single vertex. [TZ98] vertex transitive graph The group of isomorphisms from a graph G to itself is the automorphism group of G , Aut(G) . A graph G is vertex-transitive if Aut(G) acts transitively on V(G) . [SL99] A graph such that every pair of vertices is equivalent under some element of its automorphism group. Every nontrivial graph that is edge-transitive but not vertex-transitive contains at least 20 vertices. [EW00] Vizing's theorem χ ′ ≤ ∆ + 1 . [DW96] voltage graph = gain graph = group-labeled graph voltage vector A vector on E(G) that is linearly dependent on the rows of the incidence matrix of G. [HN97] VRP = vehicle routing problem

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so | sp-sz | t | u | v |

w | xyz |

| weight | wheel | walk A path in which edges may be repeated. [PEB00] A finite, nonempty, alternating sequence of vertices and edges v0 , e1 , v1 , e2 , . . . , vk-1 , ek , vk in a graph G such that vi -1 and vi are the end vertices of the edge ei , 1 ≤ i≤ k . v0 and vk are the end or terminal vertices of the walk; all other vertices are internal vertices. Edges and vertices may appear more than once. A walk is open if v0≠ vk ; otherwise it is closed. [HC00] FIGURE

weak product A graph product with vertices V(G1) × V(G2) and edges (u1 , v1) ↔ (u2 , v2) if and only if u1↔ u2and v1↔ v2 . [DW96] weakly binary tree A rooted tree for which the root is adjacent to at most two vertices, and all nonroot vertices are adjacent to at most three vertices. [EW00] weakly chordal graph

Having no chordless cycle of length at least 5 in G or G'. [DW96] FIGURE

weakly connected component A weakly connected component is a maximal subgraph of a directed graph such that for every pair of vertices u , v in the subgraph, there is an undirected path from u to v and a directed path from v to u . [EW00] weakly connected digraph A directed graph in which it is possible to reach any node starting from any other node by traversing edges in some direction (i.e., not necessarily in the direction they point). The nodes in a strongly connected digraph therefore must all have either outdegree or indegree of at least 1. [EW00] A directed graph is weakly connected if it is connected but not strongly connected. [SW87] A directed graph whose underlying graph is connected. [DW96] FIGURE

web graph A graph formed by connecting several concentric wheel graphs along spokes. [EW00] weight A number wij associated with the edge (i, j) of a graph G . [RND77] FIGURE

weight matrix A matrix W = [wij] where wij is the weight of the edge from vertex i to vertex j . The weigths of the nonexistent edges are generally set to 0 or 1 , depending on the application. [RND77] weighted biased graph A biased graph with a weight function (q.v.). The main point is that the weights have no effect on balance/frustration. (Often, the weights are positive real numbers.) [TZ98] weighted diameter problem Given a graph G = (V, E) , collection C of | E | not necessarily distinct non-negative integers and positive integer K , is there a one-to-one function f : E→C such that, if f(e) is taken as the length of edge e , then G has diameter K or less? [GJ79] weighted directed graph A directed graph which has a weight, or numeric value, associated with each edge. [PEB00] FIGURE

weighted frustration index Minimum weight of a deletion set. Equivalently, minimum weight of a negation set. [TZ98] weighted gain graph A gain graph with a weight function (q.v.). The main point is that the weights have no effect

on balance/frustration. (Often, the weights are positive real numbers.) [TZ98] weighted graph A graph which has a weight, or numeric value, associated with each edge. Some applications require all weights to be nonnegative or to be positive. [PEB00] FIGURE

weighted signed graph A signed graph with a weight function (q.v.). The main point is that the weights have no effect on balance/frustration. (Often, the weights are positive real numbers.) [TZ98] wheel = wheel graph A graph Wn of order n which contains a cycle of order n – 1 , and for which every node in the cycle is connected to one other node (which is known as the hub). The edges of a wheel which include the hub are called spokes. The wheel Wn can be defined as the graph K1 + Cn-1 , where K1 is the (trivial) complete graph on 1 node and Cn is the cycle graph. [EW00] FIGURE

wheel graph = wheel Whitney's 2-isomorphism theorem A characterization of the pairs of graphs whose cycle matroids are isomorphic. [DW96] Wiener index The sum of the pairwise distances between vertices. [DW96] worst-case complexity The maximum order of the running time taken over all problems of a given size. [BC79]

| # | a | b | c-cn | co | -cz | d | e | f | g | h | i | j | k | l | m-mh | mi | mj-mz | | n | o | p | q | r | s-so | sp-sz | t | u | v | w |

xyz |

x, U-fan Pairwise internally dist paths from x to distinct vertices of U . [DW96] FIGURE

zero-free chromatic number The smallest number of colors, excluding 0, with which a signed or gain graph can be properly colored. [TZ98]

Graph Theory Glossary 235163

Overview 26281t

More details 6y5l6z

Related Documents 3h463d

Graph Theory Glossary 235163

Graph Theory Bondy Murty 1r4c2b

Graph Theory With Applications 2e25v

Schaum's: Graph Theory 4a4p

Graph Theory Tutorial 4w4f1v

Graph Theory Mcq 5lv2r