# Glossary of graph theory terms

(Redirected from Glossary of graph theory)

This is a glossary of graph theory terms. Glossary of graph theory terms_sentence_1

Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges. Glossary of graph theory terms_sentence_2

## Symbols Glossary of graph theory terms_section_0

Glossary of graph theory terms_description_list_0

• Square brackets [ ]: G[S] is the induced subgraph of a graph G for vertex subset S.Glossary of graph theory terms_item_0_0
• Prime symbol ': The prime symbol is often used to modify notation for graph invariants so that it applies to the line graph instead of the given graph. For instance, α(G) is the independence number of a graph; α′(G) is the matching number of the graph, which equals the independence number of its line graph. Similarly, χ(G) is the chromatic number of a graph; χ ′(G) is the chromatic index of the graph, which equals the chromatic number of its line graph.Glossary of graph theory terms_item_0_1

## B Glossary of graph theory terms_section_2

Glossary of graph theory terms_description_list_1

• bag: One of the sets of vertices in a tree decomposition.Glossary of graph theory terms_item_1_2
• balanced: A bipartite or multipartite graph is balanced if each two subsets of its vertex partition have sizes within one of each other.Glossary of graph theory terms_item_1_3
• bandwidth: The bandwidth of a graph G is the minimum, over all orderings of vertices of G, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of G, chosen to minimize the clique size.Glossary of graph theory terms_item_1_4
• biclique: Synonym for complete bipartite graph or complete bipartite subgraph; see complete.Glossary of graph theory terms_item_1_5
• biconnected: Usually a synonym for 2-vertex-connected, but sometimes includes K2 though it is not 2-connected. See connected; for biconnected components, see component.Glossary of graph theory terms_item_1_6
• binding number: The smallest possible ratio of the number of neighbors of a proper subset of vertices to the size of the subset.Glossary of graph theory terms_item_1_7
• bipartite: A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written G = (U,V,E) where U and V are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.Glossary of graph theory terms_item_1_8
• biregular: A biregular graph is a bipartite graph in which there are only two different vertex degrees, one for each set of the vertex bipartition.Glossary of graph theory terms_item_1_9
• block: 1.  A block of a graph G is a maximal subgraph which is either an isolated vertex, a bridge edge, or a 2-connected subgraph. If a block is 2-connected, every pair of vertices in it belong to a common cycle. Every edge of a graph belongs in exactly one block.Glossary of graph theory terms_item_1_10
• 2.  The block graph of a graph G is another graph whose vertices are the blocks of G, with an edge connecting two vertices when the corresponding blocks share an articulation point; that is, it is the intersection graph of the blocks of G. The block graph of any graph is a forest.Glossary of graph theory terms_item_1_11
• 3.  The block-cut (or block-cutpoint) graph of a graph G has as vertices the blocks and the articulation points separating them and its edges connect blocks to the articulation points within those blocks. The block-cut graph is a forest and if G is connected it is a tree, called the block-cut tree of G.Glossary of graph theory terms_item_1_12
• 4.  A block graph (also called a clique tree if connected, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete graphs. A forest is a block graph; so in particular the block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.Glossary of graph theory terms_item_1_13
• bond: A minimal cut-set: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.Glossary of graph theory terms_item_1_14
• book: 1.  A book, book graph, or triangular book is a complete tripartite graph K1,1,n; a collection of n triangles joined at a shared edge.Glossary of graph theory terms_item_1_15
• 2.  Another type of graph, also called a book, or a quadrilateral book, is a collection of 4-cycles joined at a shared edge; the Cartesian product of a star with an edge.Glossary of graph theory terms_item_1_16
• 3.  A book embedding is an embedding of a graph onto a topological book, a space formed by joining a collection of half-planes along a shared line. Usually, the vertices of the embedding are required to be on the line, which is called the spine of the embedding, and the edges of the embedding are required to lie within a single half-plane, one of the pages of the book.Glossary of graph theory terms_item_1_17
• bramble: A bramble is a collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an edge. The order of a bramble is the smallest size of a set of vertices that has a nonempty intersection with all of the subgraphs. The treewidth of a graph is the maximum order of any of its brambles.Glossary of graph theory terms_item_1_18
• branch-decomposition: A branch-decomposition of G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree with its leaves labeled by the edges of G. The width of a branch-decomposition is the maximum, over edges e of this binary tree, of the number of shared vertices between the subgraphs determined by the edges of G in the two subtrees separated by e. The branchwidth of G is the minimum width of any branch-decomposition of G.Glossary of graph theory terms_item_1_19
• branchwidth: See branch-decomposition.Glossary of graph theory terms_item_1_20
• bridge: 1.  A bridge, isthmus, or cut edge is an edge whose removal would disconnect the graph. A bridgeless graph is one that has no bridges; equivalently, a 2-edge-connected graph.Glossary of graph theory terms_item_1_21
• 2.  Especially in the context of planarity testing, a bridge of a cycle is a maximal subgraph that is disjoint from the cycle and in which each two edges belong to a path that is internally disjoint from the cycle. A chord is a one-edge bridge. A peripheral cycle is a cycle with at most one bridge; it must be a face in any planar embedding of its graph.Glossary of graph theory terms_item_1_22
• 3.  A bridge of a cycle can also mean a path that connects two vertices of a cycle but is shorter than either of the paths in the cycle connecting the same two vertices. A bridged graph is a graph in which every cycle of four or more vertices has a bridge.Glossary of graph theory terms_item_1_23
• bridgeless: A bridgeless graph is a graph that has no bridge edges; that is, a 2-edge-connected graph.Glossary of graph theory terms_item_1_24
• butterfly: 1.  The butterfly graph has five vertices and six edges; it is formed by two triangles that share a vertex.Glossary of graph theory terms_item_1_25
• 2.  The butterfly network is a graph used as a network architecture in distributed computing, closely related to the cube-connected cycles.Glossary of graph theory terms_item_1_26

## D Glossary of graph theory terms_section_4

Glossary of graph theory terms_description_list_2

• DAG: Abbreviation for directed acyclic graph, a directed graph without any directed cycles.Glossary of graph theory terms_item_2_27
• deck: The multiset of graphs formed from a single graph G by deleting a single vertex in all possible ways, especially in the context of the reconstruction conjecture. An edge-deck is formed in the same way by deleting a single edge in all possible ways. The graphs in a deck are also called cards. See also critical (graphs that have a property that is not held by any card) and hypo- (graphs that do not have a property that is held by all cards).Glossary of graph theory terms_item_2_28
• decomposition: See tree decomposition, path decomposition, or branch-decomposition.Glossary of graph theory terms_item_2_29
• degeneracy: A k-degenerate graph is an undirected graph in which every induced subgraph has minimum degree at most k. The degeneracy of a graph is the smallest k for which it is k-degenerate. A degeneracy ordering is an ordering of the vertices such that each vertex has minimum degree in the induced subgraph of it and all later vertices; in a degeneracy ordering of a k-degenerate graph, every vertex has at most k later neighbours. Degeneracy is also known as the k-core number, width, and linkage, and one plus the degeneracy is also called the coloring number or Szekeres–Wilf number. k-degenerate graphs have also been called k-inductive graphs.Glossary of graph theory terms_item_2_30
• degree: 1.  The degree of a vertex in a graph is its number of incident edges. The degree of a graph G (or its maximum degree) is the maximum of the degrees of its vertices, often denoted Δ(G); the minimum degree of G is the minimum of its vertex degrees, often denoted δ(G). Degree is sometimes called valency; the degree of v in G may be denoted dG(v), d(G), or deg(v). The total degree is the sum of the degrees of all vertices; by the handshaking lemma it is an even number. The degree sequence is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing edges).Glossary of graph theory terms_item_2_31
• 2.  The homomorphism degree of a graph is a synonym for its Hadwiger number, the order of the largest clique minor.Glossary of graph theory terms_item_2_32
• Δ, δ: Δ(G) (using the Greek letter delta) is the maximum degree of a vertex in G, and δ(G) is the minimum degree; see degree.Glossary of graph theory terms_item_2_33
• density: In a graph of n nodes, the density is the ratio of the number of edges of the graph to the number of edges in a complete graph on n nodes. See dense graph.Glossary of graph theory terms_item_2_34
• depth: The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use depth as a synonym for the level of a node.Glossary of graph theory terms_item_2_35
• diameter: The diameter of a connected graph is the maximum length of a shortest path. That is, it is the maximum of the distances between pairs of vertices in the graph. If the graph has weights on its edges, then its weighted diameter measures path length by the sum of the edge weights along a path, while the unweighted diameter measures path length by the number of edges. For disconnected graphs, definitions vary: the diameter may be defined as infinite, or as the largest diameter of a connected component, or it may be undefined.Glossary of graph theory terms_item_2_36
• diamond: The diamond graph is an undirected graph with four vertices and five edges.Glossary of graph theory terms_item_2_37
• diconnected: Strongly connected. (Not to be confused with disconnected)Glossary of graph theory terms_item_2_38
• digon: A digon is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in simple undirected graphs as they require repeating the same edge twice, which violates the definition of simple.Glossary of graph theory terms_item_2_39
• digraph: Synonym for directed graph.Glossary of graph theory terms_item_2_40
• dipath: See directed path.Glossary of graph theory terms_item_2_41
• direct predecessor: The tail of a directed edge whose head is the given vertex.Glossary of graph theory terms_item_2_42
• direct successor: The head of a directed edge whose tail is the given vertex.Glossary of graph theory terms_item_2_43
• directed: A directed graph is one in which the edges have a distinguished direction, from one vertex to another. In a mixed graph, a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.Glossary of graph theory terms_item_2_44
• directed arc: See arrow.Glossary of graph theory terms_item_2_45
• directed edge: See arrow.Glossary of graph theory terms_item_2_46
• directed line: See arrow.Glossary of graph theory terms_item_2_47
• directed path: A path in which all the edges have the same direction. If a directed path leads from vertex x to vertex y, x is a predecessor of y, y is a successor of x, and y is said to be reachable from x.Glossary of graph theory terms_item_2_48
• direction: 1.  The asymmetric relation between two adjacent vertices in a graph, represented as an arrow.Glossary of graph theory terms_item_2_49
• 2.  The asymmetric relation between two vertices in a directed path.Glossary of graph theory terms_item_2_50
• disconnect: Cause to be disconnected.Glossary of graph theory terms_item_2_51
• disconnected: Not connected.Glossary of graph theory terms_item_2_52
• disjoint: 1.  Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.Glossary of graph theory terms_item_2_53
• 2.  The disjoint union of two or more graphs is a graph whose vertex and edge sets are the disjoint unions of the corresponding sets.Glossary of graph theory terms_item_2_54
• distance: The distance between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.Glossary of graph theory terms_item_2_55
• domatic: A domatic partition of a graph is a partition of the vertices into dominating sets. The domatic number of the graph is the maximum number of dominating sets in such a partition.Glossary of graph theory terms_item_2_56
• dominating: A dominating set is a set of vertices that includes or is adjacent to every vertex in the graph; not to be confused with a vertex cover, a vertex set that is incident to all edges in the graph. Important special types of dominating sets include independent dominating sets (dominating sets that are also independent sets) and connected dominating sets (dominating sets that induced connected subgraphs). A single-vertex dominating set may also be called a universal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.Glossary of graph theory terms_item_2_57

## E Glossary of graph theory terms_section_5

Glossary of graph theory terms_description_list_3

• E: E(G) is the edge set of G; see edge set.Glossary of graph theory terms_item_3_58
• ear: An ear of a graph is a path whose endpoints may coincide but in which otherwise there are no repetitions of vertices or edges.Glossary of graph theory terms_item_3_59
• ear decomposition: An ear decomposition is a partition of the edges of a graph into a sequence of ears, each of whose endpoints (after the first one) belong to a previous ear and each of whose interior points do not belong to any previous ear. An open ear is a simple path (an ear without repeated vertices), and an open ear decomposition is an ear decomposition in which each ear after the first is open; a graph has an open ear decomposition if and only if it is biconnected. An ear is odd if it has an odd number of edges, and an odd ear decomposition is an ear decomposition in which each ear is odd; a graph has an odd ear decomposition if and only if it is factor-critical.Glossary of graph theory terms_item_3_60
• eccentricity: The eccentricity of a vertex is the farthest distance from it to any other vertex.Glossary of graph theory terms_item_3_61
• edge: An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are also called arcs or arrows. In an undirected simple graph, an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices x and y is sometimes written xy.Glossary of graph theory terms_item_3_62
• edge cut: A set of edges whose removal disconnects the graph. A one-edge cut is called a bridge, isthmus, or cut edge.Glossary of graph theory terms_item_3_63
• edge set: The set of edges of a given graph G, sometimes denoted by E(G).Glossary of graph theory terms_item_3_64
• edgeless graph: The edgeless graph or totally disconnected graph on a given set of vertices is the graph that has no edges. It is sometimes called the empty graph, but this term can also refer to a graph with no vertices.Glossary of graph theory terms_item_3_65
• embedding: A graph embedding is a topological representation of a graph as a subset of a topological space with each vertex represented as a point, each edge represented as a curve having the endpoints of the edge as endpoints of the curve, and no other intersections between vertices or edges. A planar graph is a graph that has such an embedding onto the Euclidean plane, and a toroidal graph is a graph that has such an embedding onto a torus. The genus of a graph is the minimum possible genus of a two-dimensional manifold onto which it can be embedded.Glossary of graph theory terms_item_3_66
• empty graph: 1.  An edgeless graph on a nonempty set of vertices.Glossary of graph theory terms_item_3_67
• 2.  The order-zero graph, a graph with no vertices and no edges.Glossary of graph theory terms_item_3_68
• end: An end of an infinite graph is an equivalence class of rays, where two rays are equivalent if there is a third ray that includes infinitely many vertices from both of them.Glossary of graph theory terms_item_3_69
• endpoint: One of the two vertices joined by a given edge, or one of the first or last vertex of a walk, trail or path. The first endpoint of a given directed edge is called the tail and the second endpoint is called the head.Glossary of graph theory terms_item_3_70
• enumeration: Graph enumeration is the problem of counting the graphs in a given class of graphs, as a function of their order. More generally, enumeration problems can refer either to problems of counting a certain class of combinatorial objects (such as cliques, independent sets, colorings, or spanning trees), or of algorithmically listing all such objects.Glossary of graph theory terms_item_3_71
• Eulerian: An Eulerian path is a walk that uses every edge of a graph exactly once. An Eulerian circuit (also called an Eulerian cycle or an Euler tour) is a closed walk that uses every edge exactly once. An Eulerian graph is a graph that has an Eulerian circuit. For an undirected graph, this means that the graph is connected and every vertex has even degree. For a directed graph, this means that the graph is strongly connected and every vertex has in-degree equal to the out-degree. In some cases, the connectivity requirement is loosened, and a graph meeting only the degree requirements is called Eulerian.Glossary of graph theory terms_item_3_72
• even: Divisible by two; for instance, an even cycle is a cycle whose length is even.Glossary of graph theory terms_item_3_73
• expander: An expander graph is a graph whose edge expansion, vertex expansion, or spectral expansion is bounded away from zero.Glossary of graph theory terms_item_3_74
• expansion: 1.  The edge expansion, isoperimetric number, or Cheeger constant of a graph G is the minimum ratio, over subsets S of at most half of the vertices of G, of the number of edges leaving S to the number of vertices in S.Glossary of graph theory terms_item_3_75
• 2.  The vertex expansion, vertex isoperimetric number, or magnification of a graph G is the minimum ratio, over subsets S of at most half of the vertices of G, of the number of vertices outside but adjacent to S to the number of vertices in S.Glossary of graph theory terms_item_3_76
• 3.  The unique neighbor expansion of a graph G is the minimum ratio, over subsets of at most half of the vertices of G, of the number of vertices outside S but adjacent to a unique vertex in S to the number of vertices in S.Glossary of graph theory terms_item_3_77
• 4.  The spectral expansion of a d-regular graph G is the spectral gap between the largest eigenvalue d of its adjacency matrix and the second-largest eigenvalue.Glossary of graph theory terms_item_3_78
• 5.  A family of graphs has bounded expansion if all its r-shallow minors have a ratio of edges to vertices bounded by a function of r, and polynomial expansion if the function of r is a polynomial.Glossary of graph theory terms_item_3_79

## F Glossary of graph theory terms_section_6

Glossary of graph theory terms_description_list_4

• face: In a plane graph or graph embedding, a connected component of the subset of the plane or surface of the embedding that is disjoint from the graph. For an embedding in the plane, all but one face will be bounded; the one exceptional face that extends to infinity is called the outer face.Glossary of graph theory terms_item_4_80
• factor: A factor of a graph is a spanning subgraph: a subgraph that includes all of the vertices of the graph. The term is primarily used in the context of regular subgraphs: a k-factor is a factor that is k-regular. In particular, a 1-factor is the same thing as a perfect matching. A factor-critical graph is a graph for which deleting any one vertex produces a graph with a 1-factor.Glossary of graph theory terms_item_4_81
• factorization: A graph factorization is a partition of the edges of the graph into factors; a k-factorization is a partition into k-factors. For instance a 1-factorization is an edge coloring with the additional property that each vertex is incident to an edge of each color.Glossary of graph theory terms_item_4_82
• family: A synonym for class.Glossary of graph theory terms_item_4_83
• finite: A graph is finite if it has a finite number of vertices and a finite number of edges. Many sources assume that all graphs are finite without explicitly saying so. A graph is locally finite if each vertex has a finite number of incident edges. An infinite graph is a graph that is not finite: it has infinitely many vertices, infinitely many edges, or both.Glossary of graph theory terms_item_4_84
• first order: The first order logic of graphs is a form of logic in which variables represent vertices of a graph, and there exists a binary predicate to test whether two vertices are adjacent. To be distinguished from second order logic, in which variables can also represent sets of vertices or edges.Glossary of graph theory terms_item_4_85
• -flap: For a set of vertices X, an X-flap is a connected component of the induced subgraph formed by deleting X. The flap terminology is commonly used in the context of havens, functions that map small sets of vertices to their flaps. See also the bridge of a cycle, which is either a flap of the cycle vertices or a chord of the cycle.Glossary of graph theory terms_item_4_86
• forbidden: A forbidden graph characterization is a characterization of a family of graphs as being the graphs that do not have certain other graphs as subgraphs, induced subgraphs, or minors. If H is one of the graphs that does not occur as a subgraph, induced subgraph, or minor, then H is said to be forbidden.Glossary of graph theory terms_item_4_87
• forest: A forest is an undirected graph without cycles (a disjoint union of unrooted trees), or a directed graph formed as a disjoint union of rooted trees.Glossary of graph theory terms_item_4_88
• Frucht: 1.  Robert FruchtGlossary of graph theory terms_item_4_89
• 2.  The Frucht graph, one of the two smallest cubic graphs with no nontrivial symmetries.Glossary of graph theory terms_item_4_90
• 3.  Frucht's theorem that every finite group is the group of symmetries of a finite graph.Glossary of graph theory terms_item_4_91
• full: Synonym for induced.Glossary of graph theory terms_item_4_92
• functional graph: A functional graph is a directed graph where every vertex has out-degree one. Equivalently, a functional graph is a maximal directed pseudoforest.Glossary of graph theory terms_item_4_93

## G Glossary of graph theory terms_section_7

Glossary of graph theory terms_description_list_5

• G: A variable often used to denote a graph.Glossary of graph theory terms_item_5_94
• genus: The genus of a graph is the minimum genus of a surface onto which it can be embedded; see embedding.Glossary of graph theory terms_item_5_95
• geodesic: As a noun, a geodesic is a synonym for a shortest path. When used as an adjective, it means related to shortest paths or shortest path distances.Glossary of graph theory terms_item_5_96
• giant: In the theory of random graphs, a giant component is a connected component that contains a constant fraction of the vertices of the graph. In standard models of random graphs, there is typically at most one giant component.Glossary of graph theory terms_item_5_97
• girth: The girth of a graph is the length of its shortest cycle.Glossary of graph theory terms_item_5_98
• graph: The fundamental object of study in graph theory, a system of vertices connected in pairs by edges. Often subdivided into directed graphs or undirected graphs according to whether the edges have an orientation or not. Mixed graphs include both types of edges.Glossary of graph theory terms_item_5_99
• greedy: Produced by a greedy algorithm. For instance, a greedy coloring of a graph is a coloring produced by considering the vertices in some sequence and assigning each vertex the first available color.Glossary of graph theory terms_item_5_100
• Grötzsch: 1.  Herbert GrötzschGlossary of graph theory terms_item_5_101
• 2.  The Grötzsch graph, the smallest triangle-free graph requiring four colors in any proper coloring.Glossary of graph theory terms_item_5_102
• 3.  Grötzsch's theorem that triangle-free planar graphs can always be colored with at most three colors.Glossary of graph theory terms_item_5_103
• Grundy number: 1.  The Grundy number of a graph is the maximum number of colors produced by a greedy coloring, with a badly-chosen vertex ordering.Glossary of graph theory terms_item_5_104

## H Glossary of graph theory terms_section_8

Glossary of graph theory terms_description_list_6

• H: A variable often used to denote a graph, especially when another graph has already been denoted by G.Glossary of graph theory terms_item_6_105
• H-coloring: An H-coloring of a graph G (where H is also a graph) is a homomorphism from H to G.Glossary of graph theory terms_item_6_106
• H-free: A graph is H-free if it does not have an induced subgraph isomorphic to H, that is, if H is a forbidden induced subgraph. The H-free graphs are the family of all graphs (or, often, all finite graphs) that are H-free. For instance the triangle-free graphs are the graphs that do not have a triangle graph as a subgraph. The property of being H-free is always hereditary. A graph is H-minor-free if it does not have a minor isomorphic to H.Glossary of graph theory terms_item_6_107
• 2.  The Hadwiger number of a graph is the order of the largest complete minor of the graph. It is also called the contraction clique number or the homomorphism degree.Glossary of graph theory terms_item_6_109
• 3.  The Hadwiger conjecture is the conjecture that the Hadwiger number is never less than the chromatic number.Glossary of graph theory terms_item_6_110
• Hamiltonian: A Hamiltonian path or Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.Glossary of graph theory terms_item_6_111
• haven: A k-haven is a function that maps every set X of fewer than k vertices to one of its flaps, often satisfying additional consistency conditions. The order of a haven is the number k. Havens can be used to characterize the treewidth of finite graphs and the ends and Hadwiger numbers of infinite graphs.Glossary of graph theory terms_item_6_112
• height: 1.  The height of a node in a rooted tree is the number of edges in a maximal path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf.Glossary of graph theory terms_item_6_113
• 2.  The height of a rooted tree is the height of its root. That is, the height of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf.Glossary of graph theory terms_item_6_114
• 3.  The height of a directed acyclic graph is the maximal length of a directed path in this graph.Glossary of graph theory terms_item_6_115
• hereditary: A hereditary property of graphs is a property that is closed under induced subgraphs: if G has a hereditary property, then so must every induced subgraph of G. Compare monotone (closed under all subgraphs) or minor-closed (closed under minors).Glossary of graph theory terms_item_6_116
• hexagon: A simple cycle consisting of exactly six edges and six vertices.Glossary of graph theory terms_item_6_117
• hole: A hole is an induced cycle of length four or more. An odd hole is a hole of odd length. An anti-hole is an induced subgraph of order four whose complement is a cycle; equivalently, it is a hole in the complement graph. This terminology is mainly used in the context of perfect graphs, which are characterized by the strong perfect graph theorem as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the chordal graphs.Glossary of graph theory terms_item_6_118
• homomorphic equivalence: Two graphs are homomorphically equivalent if there exist two homomorphisms, one from each graph to the other graph.Glossary of graph theory terms_item_6_119
• homomorphism: 1.  A graph homomorphism is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory. A proper graph coloring can equivalently be described as a homomorphism to a complete graph.Glossary of graph theory terms_item_6_120
• 2.  The homomorphism degree of a graph is a synonym for its Hadwiger number, the order of the largest clique minor.Glossary of graph theory terms_item_6_121
• hyperedge: An edge in a hypergraph, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.Glossary of graph theory terms_item_6_122
• hypercube: A hypercube graph is a graph formed from the vertices and edges of a geometric hypercube.Glossary of graph theory terms_item_6_123
• hypergraph: A hypergraph is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.Glossary of graph theory terms_item_6_124
• hypo-: This prefix, in combination with a graph property, indicates a graph that does not have the property but such that every subgraph formed by deleting a single vertex does have the property. For instance, a hypohamiltonian graph is one that does not have a Hamiltonian cycle, but for which every one-vertex deletion produces a Hamiltonian subgraph. Compare critical, used for graphs which have a property but for which every one-vertex deletion does not.Glossary of graph theory terms_item_6_125

## I Glossary of graph theory terms_section_9

Glossary of graph theory terms_description_list_7

• in-degree: The number of incoming edges in a directed graph; see degree.Glossary of graph theory terms_item_7_126
• incidence: An incidence in a graph is a vertex-edge pair such that the vertex is an endpoint of the edge.Glossary of graph theory terms_item_7_127
• incidence matrix: The incidence matrix of a graph is a matrix whose rows are indexed by vertices of the graph, and whose columns are indexed by edges, with a one in the cell for row i and column j when vertex i and edge j are incident, and a zero otherwise.Glossary of graph theory terms_item_7_128
• incident: The relation between an edge and one of its endpoints.Glossary of graph theory terms_item_7_129
• incomparability: An incomparability graph is the complement of a comparability graph; see comparability.Glossary of graph theory terms_item_7_130
• independent: 1.  An independent set is a set of vertices that induces an edgeless subgraph. It may also be called a stable set or a coclique. The independence number α(G) is the size of the maximum independent set.Glossary of graph theory terms_item_7_131
• 2.  In the graphic matroid of a graph, a subset of edges is independent if the corresponding subgraph is a tree or forest. In the bicircular matroid, a subset of edges is independent if the corresponding subgraph is a pseudoforest.Glossary of graph theory terms_item_7_132
• indifference: An indifference graph is another name for a proper interval graph or unit interval graph; see proper.Glossary of graph theory terms_item_7_133
• induced: An induced subgraph or full subgraph of a graph is a subgraph formed from a subset of vertices and from all of the edges that have both endpoints in the subset. Special cases include induced paths and induced cycles, induced subgraphs that are paths or cycles.Glossary of graph theory terms_item_7_134
• inductive: Synonym for degenerate.Glossary of graph theory terms_item_7_135
• infinite: An infinite graph is one that is not finite; see finite.Glossary of graph theory terms_item_7_136
• internal: A vertex of a path or tree is internal if it is not a leaf; that is, if its degree is greater than one. Two paths are internally disjoint (some people call it independent) if they do not have any vertex in common, except the first and last ones.Glossary of graph theory terms_item_7_137
• intersection: 1.  The intersection of two graphs is their largest common subgraph, the graph formed by the vertices and edges that belong to both graphs.Glossary of graph theory terms_item_7_138
• 2.  An intersection graph is a graph whose vertices correspond to sets or geometric objects, with an edge between two vertices exactly when the corresponding two sets or objects have a nonempty intersection. Several classes of graphs may be defined as the intersection graphs of certain types of objects, for instance chordal graphs (intersection graphs of subtrees of a tree), circle graphs (intersection graphs of chords of a circle), interval graphs (intersection graphs of intervals of a line), line graphs (intersection graphs of the edges of a graph), and clique graphs (intersection graphs of the maximal cliques of a graph). Every graph is an intersection graph for some family of sets, and this family is called an intersection representation of the graph. The intersection number of a graph G is the minimum total number of elements in any intersection representation of G.Glossary of graph theory terms_item_7_139
• interval: An interval graph is an intersection graph of intervals of a line.Glossary of graph theory terms_item_7_140
• interval thickness: A synonym for pathwidth.Glossary of graph theory terms_item_7_141
• invariant: A synonym of pathwidth.Glossary of graph theory terms_item_7_142
• inverted arrow: An arrow with an opposite direction compared to another arrow. The arrow (y, x) is the inverted arrow of the arrow (x, y).Glossary of graph theory terms_item_7_143
• isolated: An isolated vertex of a graph is a vertex whose degree is zero, that is, a vertex with no incident edges.Glossary of graph theory terms_item_7_144
• isomorphic: Two graphs are isomorphic if there is an isomorphism between them; see isomorphism.Glossary of graph theory terms_item_7_145
• isomorphism: A graph isomorphism is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.Glossary of graph theory terms_item_7_146
• isoperimetric: See expansion.Glossary of graph theory terms_item_7_147
• isthmus: Synonym for bridge, in the sense of an edge whose removal disconnects the graph.Glossary of graph theory terms_item_7_148

## K Glossary of graph theory terms_section_10

Glossary of graph theory terms_description_list_8

• K: For the notation for complete graphs, complete bipartite graphs, and complete multipartite graphs, see complete.Glossary of graph theory terms_item_8_149
• κ: κ(G) (using the Greek letter kappa) is the order of the maximum clique in G; see clique.Glossary of graph theory terms_item_8_150
• kernel: A kernel of a directed graph is a set of vertices which is both stable and absorbing.Glossary of graph theory terms_item_8_151
• knot: An inescapable section of a directed graph. See knot (mathematics) and knot theory.Glossary of graph theory terms_item_8_152

## L Glossary of graph theory terms_section_11

Glossary of graph theory terms_description_list_9

• L: L(G) is the line graph of G; see line.Glossary of graph theory terms_item_9_153
• label: 1.  Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. The terms vertex-labeled or edge-labeled may be used to specify which objects of a graph have labels. Graph labeling refers to several different problems of assigning labels to graphs subject to certain constraints. See also graph coloring, in which the labels are interpreted as colors.Glossary of graph theory terms_item_9_154
• 2.  In the context of graph enumeration, the vertices of a graph are said to be labeled if they are all distinguishable from each other. For instance, this can be made to be true by fixing a one-to-one correspondence between the vertices and the integers from 1 to the order of the graph. When vertices are labeled, graphs that are isomorphic to each other (but with different vertex orderings) are counted as separate objects. In contrast, when the vertices are unlabeled, graphs that are isomorphic to each other are not counted separately.Glossary of graph theory terms_item_9_155
• leaf: 1.  A leaf vertex or pendant vertex (especially in a tree) is a vertex whose degree is 1. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour.Glossary of graph theory terms_item_9_156
• 2.  A leaf power of a tree is a graph whose vertices are the leaves of the tree and whose edges connect leaves whose distance in the tree is at most a given threshold.Glossary of graph theory terms_item_9_157
• length: In an unweighted graph, the length of a cycle, path, or walk is the number of edges it uses. In a weighted graph, it may instead be the sum of the weights of the edges that it uses. Length is used to define the shortest path, girth (shortest cycle length), and longest path between two vertices in a graph.Glossary of graph theory terms_item_9_158
• level: 1.  This is the depth of a node plus 1, although some define it instead to be synonym of depth. A node's level in a rooted tree is the number of nodes in the path from the root to the node. For instance, the root has level 1 and any one of its adjacent nodes has level 2.Glossary of graph theory terms_item_9_159
• 2.  A set of all node having the same level or depth.Glossary of graph theory terms_item_9_160
• line: A synonym for an undirected edge. The line graph L(G) of a graph G is a graph with a vertex for each edge of G and an edge for each pair of edge that share an endpoint in G.Glossary of graph theory terms_item_9_161
• linkage: A synonym for degeneracy.Glossary of graph theory terms_item_9_162
• list: 1.  An adjacency list is a computer representation of graphs for use in graph algorithms.Glossary of graph theory terms_item_9_163
• 2.  List coloring is a variation of graph coloring in which each vertex has a list of available colors.Glossary of graph theory terms_item_9_164
• local: A local property of a graph is a property that is determined only by the neighbourhoods of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.Glossary of graph theory terms_item_9_165
• loop: A loop or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length 1. These are not allowed in simple graphs.Glossary of graph theory terms_item_9_166

## M Glossary of graph theory terms_section_12

Glossary of graph theory terms_description_list_10

• magnification: Synonym for vertex expansion.Glossary of graph theory terms_item_10_167
• matching: A matching is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A perfect matching or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A maximum matching is a matching that uses as many edges as possible; the matching number α′(G) of a graph G is the number of edges in a maximum matching. A maximal matching is a matching to which no additional edges can be added.Glossary of graph theory terms_item_10_168
• maximal: 1.  A subgraph of given graph G is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of G also has the same property. That is, it is a maximal element of the subgraphs with the property. For instance, a maximal clique is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.Glossary of graph theory terms_item_10_169
• 2.  A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a maximal planar graph is a planar graph such that adding any more edges to it would create a non-planar graph.Glossary of graph theory terms_item_10_170
• maximum: A subgraph of a given graph G is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a maximum clique is any of the largest cliques in a given graph.Glossary of graph theory terms_item_10_171
• median: 1.  A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and modular graphs.Glossary of graph theory terms_item_10_172
• 2.  A median graph is a graph in which every three vertices have a unique median.Glossary of graph theory terms_item_10_173
• Meyniel: 1.  Henri Meyniel, French graph theorist.Glossary of graph theory terms_item_10_174
• 2.  A Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords.Glossary of graph theory terms_item_10_175
• minimal: A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a minimal element of the subgraphs with the property.Glossary of graph theory terms_item_10_176
• minimum cut: A cut whose cut-set has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the max-flow min-cut theorem.Glossary of graph theory terms_item_10_177
• minor: A graph H is a minor of another graph G if H can be obtained by deleting edges or vertices from G and contracting edges in G. It is a shallow minor if it can be formed as a minor in such a way that the subgraphs of G that were contracted to form vertices of H all have small diameter. H is a topological minor of G if G has a subgraph that is a subdivision of H. A graph is H-minor-free if it does not have H as a minor. A family of graphs is minor-closed if it is closed under minors; the Robertson–Seymour theorem characterizes minor-closed families as having a finite set of forbidden minors.Glossary of graph theory terms_item_10_178
• mixed: A mixed graph is a graph that may include both directed and undirected edges.Glossary of graph theory terms_item_10_179
• modular: 1.  Modular graph, a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.Glossary of graph theory terms_item_10_180
• 2.  Modular decomposition, a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.Glossary of graph theory terms_item_10_181
• 3.  Modularity of a graph clustering, the difference of the number of cross-cluster edges from its expected value.Glossary of graph theory terms_item_10_182
• monotone: A monotone property of graphs is a property that is closed under subgraphs: if G has a hereditary property, then so must every subgraph of G. Compare hereditary (closed under induced subgraphs) or minor-closed (closed under minors).Glossary of graph theory terms_item_10_183
• Moore graph: A Moore graph is a regular graph for which the Moore bound is met exactly. The Moore bound is an inequality relating the degree, diameter, and order of a graph, proved by Edward F. Moore. Every Moore graph is a cage.Glossary of graph theory terms_item_10_184
• multigraph: A multigraph is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.Glossary of graph theory terms_item_10_185
• multiple adjacency: A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a multigraph.Glossary of graph theory terms_item_10_186
• multiplicity: The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.Glossary of graph theory terms_item_10_187

## N Glossary of graph theory terms_section_13

Glossary of graph theory terms_description_list_11

• N: 1.  For the notation for open and closed neighborhoods, see neighbourhood.Glossary of graph theory terms_item_11_188
• 2.  A lower-case n is often used (especially in computer science) to denote the number of vertices in a given graph.Glossary of graph theory terms_item_11_189
• neighbour: A vertex that is adjacent to a given vertex.Glossary of graph theory terms_item_11_190
• neighbourhood: The open neighbourhood (or neighborhood) of a vertex v is the subgraph induced by all vertices that are adjacent to v. The closed neighbourhood is defined in the same way but also includes v itself. The open neighborhood of v in G may be denoted NG(v) or N(v), and the closed neighborhood may be denoted NG[v] or N[v]. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.Glossary of graph theory terms_item_11_191
• network: A graph in which attributes (e.g. names) are associated with the nodes and/or edges.Glossary of graph theory terms_item_11_192
• node: A synonym for vertex.Glossary of graph theory terms_item_11_193
• non-edge: A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.Glossary of graph theory terms_item_11_194
• null graph: See empty graph.Glossary of graph theory terms_item_11_195

## O Glossary of graph theory terms_section_14

Glossary of graph theory terms_description_list_12

• odd: 1.  An odd cycle is a cycle whose length is odd. The odd girth of a non-bipartite graph is the length of its shortest odd cycle. An odd hole is a special case of an odd cycle: one that is induced and has four or more vertices.Glossary of graph theory terms_item_12_196
• 2.  An odd vertex is a vertex whose degree is odd. By the handshaking lemma every finite undirected graph has an even number of odd vertices.Glossary of graph theory terms_item_12_197
• 3.  An odd ear is a simple path or simple cycle with an odd number of edges, used in odd ear decompositions of factor-critical graphs; see ear.Glossary of graph theory terms_item_12_198
• 4.  An odd chord is an edge connecting two vertices that are an odd distance apart in an even cycle. Odd chords are used to define strongly chordal graphs.Glossary of graph theory terms_item_12_199
• 5.  An odd graph is a special case of a Kneser graph, having one vertex for each (n − 1)-element subset of a (2n − 1)-element set, and an edge connecting two subsets when their corresponding sets are disjoint.Glossary of graph theory terms_item_12_200
• open: 1.  See neighbourhood.Glossary of graph theory terms_item_12_201
• 2.  See walk.Glossary of graph theory terms_item_12_202
• order: 1.  The order of a graph G is the number of its vertices, |V(G)|. The variable n is often used for this quantity. See also size, the number of edges.Glossary of graph theory terms_item_12_203
• 2.  A type of logic of graphs; see first order and second order.Glossary of graph theory terms_item_12_204
• 3.  An order or ordering of a graph is an arrangement of its vertices into a sequence, especially in the context of topological ordering (an order of a directed acyclic graph in which every edge goes from an earlier vertex to a later vertex in the order) and degeneracy ordering (an order in which each vertex has minimum degree in the induced subgraph of it and all later vertices).Glossary of graph theory terms_item_12_205
• 4.  For the order of a haven or bramble, see haven and bramble.Glossary of graph theory terms_item_12_206
• oriented: 1.  An orientation of an undirected graph is an assignment of directions to its edges, making it into a directed graph. An oriented graph is one that has been assigned an orientation. So, for instance, a polytree is an oriented tree; it differs from a directed tree (an arborescence) in that there is no requirement of consistency in the directions of its edges. Other special types of orientation include tournaments, orientations of complete graphs; strong orientations, orientations that are strongly connected; acyclic orientations, orientations that are acyclic; Eulerian orientations, orientations that are Eulerian; and transitive orientations, orientations that are transitively closed.Glossary of graph theory terms_item_12_207
• 2.  Oriented graph, used by some authors as a synonym for a directed graph.Glossary of graph theory terms_item_12_208
• out-degree: See degree.Glossary of graph theory terms_item_12_209
• outer: See face.Glossary of graph theory terms_item_12_210
• outerplanar: An outerplanar graph is a graph that can be embedded in the plane (without crossings) so that all vertices are on the outer face of the graph.Glossary of graph theory terms_item_12_211

## P Glossary of graph theory terms_section_15

Glossary of graph theory terms_description_list_13

• path: A path may either be a walk or a walk without repeated vertices and consequently edges (also called a simple path), depending on the source. Important special cases include induced paths and shortest paths.Glossary of graph theory terms_item_13_212
• path decomposition: A path decomposition of a graph G is a tree decomposition whose underlying tree is a path. Its width is defined in the same way as for tree decompositions, as one less than the size of the largest bag. The minimum width of any path decomposition of G is the pathwidth of G.Glossary of graph theory terms_item_13_213
• pathwidth: The pathwidth of a graph G is the minimum width of a path decomposition of G. It may also be defined in terms of the clique number of an interval completion of G. It is always between the bandwidth and the treewidth of G. It is also known as interval thickness, vertex separation number, or node searching number.Glossary of graph theory terms_item_13_214
• pendant: See leaf.Glossary of graph theory terms_item_13_215
• perfect: 1.  A perfect graph is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The perfect graph theorem and strong perfect graph theorem are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.Glossary of graph theory terms_item_13_216
• 2.  A perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect graphs.Glossary of graph theory terms_item_13_217
• 3.  A perfect matching is a matching that saturates every vertex; see matching.Glossary of graph theory terms_item_13_218
• 4.  A perfect 1-factorization is a partition of the edges of a graph into perfect matchings so that each two matchings form a Hamiltonian cycle.Glossary of graph theory terms_item_13_219
• peripheral: 1.  A peripheral cycle or non-separating cycle is a cycle with at most one bridge.Glossary of graph theory terms_item_13_220
• 2.  A peripheral vertex is a vertex whose eccentricity is maximum. In a tree, this must be a leaf.Glossary of graph theory terms_item_13_221
• Petersen: 1.  Julius Petersen (1839–1910), Danish graph theorist.Glossary of graph theory terms_item_13_222
• 2.  The Petersen graph, a 10-vertex 15-edge graph frequently used as a counterexample.Glossary of graph theory terms_item_13_223
• 3.  Petersen's theorem that every bridgeless cubic graph has a perfect matching.Glossary of graph theory terms_item_13_224
• planar: A planar graph is a graph that has an embedding onto the Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A k-planar graph is one that can be drawn in the plane with at most k crossings per edge.Glossary of graph theory terms_item_13_225
• polytree: A polytree is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.Glossary of graph theory terms_item_13_226
• power: 1.  A graph power G of a graph G is another graph on the same vertex set; two vertices are adjacent in G when they are at distance at most k in G. A leaf power is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.Glossary of graph theory terms_item_13_227
• 2.  Power graph analysis is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.Glossary of graph theory terms_item_13_228
• 3.  Power laws in the degree distributions of scale-free networks are a phenomenon in which the number of vertices of a given degree is proportional to a power of the degree.Glossary of graph theory terms_item_13_229
• predecessor: A vertex coming before a given vertex in a directed path.Glossary of graph theory terms_item_13_230
• proper: 1.  A proper subgraph is a subgraph that removes at least one vertex or edge relative to the whole graph; for finite graphs, proper subgraphs are never isomorphic to the whole graph, but for infinite graphs they can be.Glossary of graph theory terms_item_13_231
• 2.  A proper coloring is an assignment of colors to the vertices of a graph (a coloring) that assigns different colors to the endpoints of each edge; see color.Glossary of graph theory terms_item_13_232
• 3.  A proper interval graph or proper circular arc graph is an intersection graph of a collection of intervals or circular arcs (respectively) such that no interval or arc contains another interval or arc. Proper interval graphs are also called unit interval graphs (because they can always be represented by unit intervals) or indifference graphs.Glossary of graph theory terms_item_13_233
• property: A graph property is something that can be true of some graphs and false of others, and that depends only on the graph structure and not on incidental information such as labels. Graph properties may equivalently be described in terms of classes of graphs (the graphs that have a given property). More generally, a graph property may also be a function of graphs that is again independent of incidental information, such as the size, order, or degree sequence of a graph; this more general definition of a property is also called an invariant of the graph.Glossary of graph theory terms_item_13_234
• pseudoforest: A pseudoforest is an undirected graph in which each connected component has at most one cycle, or a directed graph in which each vertex has at most one outgoing edge.Glossary of graph theory terms_item_13_235
• pseudograph: A pseudograph is a graph or multigraph that allows self-loops.Glossary of graph theory terms_item_13_236

## Q Glossary of graph theory terms_section_16

Glossary of graph theory terms_description_list_14

• quasi-line graph: A quasi-line graph or locally co-bipartite graph is a graph in which the open neighborhood of every vertex can be partitioned into two cliques. These graphs are always claw-free and they include as a special case the line graphs. They are used in the structure theory of claw-free graphs.Glossary of graph theory terms_item_14_237
• quiver: A quiver is a directed multigraph, as used in category theory. The edges of a quiver are called arrows.Glossary of graph theory terms_item_14_238

## S Glossary of graph theory terms_section_18

Glossary of graph theory terms_description_list_15

• second order: The second order logic of graphs is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in which variables can only represent vertices.Glossary of graph theory terms_item_15_239
• saturated: See matching.Glossary of graph theory terms_item_15_240
• searching number: Node searching number is a synonym for pathwidth.Glossary of graph theory terms_item_15_241
• self-loop: Synonym for loop.Glossary of graph theory terms_item_15_242
• separating vertex: See articulation point.Glossary of graph theory terms_item_15_243
• separation number: Vertex separation number is a synonym for pathwidth.Glossary of graph theory terms_item_15_244
• simple: 1.  A simple graph is a graph without loops and without multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise.Glossary of graph theory terms_item_15_245
• 2.  A simple path or a simple cycle is a path or cycle that has no repeated vertices and consequently no repeated edges.Glossary of graph theory terms_item_15_246
• sink: A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).Glossary of graph theory terms_item_15_247
• size: The size of a graph G is the number of its edges, |E(G)|. The variable m is often used for this quantity. See also order, the number of vertices.Glossary of graph theory terms_item_15_248
• small-world network: A small-world network is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a graph where the typical distance L between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes N in the networkGlossary of graph theory terms_item_15_249
• snark: A snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.Glossary of graph theory terms_item_15_250
• source: A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).Glossary of graph theory terms_item_15_251
• space: In algebraic graph theory, several vector spaces over the binary field may be associated with a graph. Each has sets of edges or vertices for its vectors, and symmetric difference of sets as its vector sum operation. The edge space is the space of all sets of edges, and the vertex space is the space of all sets of vertices. The cut space is a subspace of the edge space that has the cut-sets of the graph as its elements. The cycle space has the Eulerian spanning subgraphs as its elements.Glossary of graph theory terms_item_15_252
• spanner: A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include geometric spanners, graphs whose vertices are points in a geometric space; tree spanners, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.Glossary of graph theory terms_item_15_253
• spanning: A subgraph is spanning when it includes all of the vertices of the given graph. Important cases include spanning trees, spanning subgraphs that are trees, and perfect matchings, spanning subgraphs that are matchings. A spanning subgraph may also be called a factor, especially (but not only) when it is regular.Glossary of graph theory terms_item_15_254
• sparse: A sparse graph is one that has few edges relative to its number of vertices. In some definitions the same property should also be true for all subgraphs of the given graph.Glossary of graph theory terms_item_15_255
• spectrum: The spectrum of a graph is the collection of eigenvalues of its adjacency matrix. Spectral graph theory is the branch of graph theory that uses spectra to analyze graphs. See also spectral expansion.Glossary of graph theory terms_item_15_256
• split: 1.  A split graph is a graph whose vertices can be partitioned into a clique and an independent set. A related class of graphs, the double split graphs, are used in the proof of the strong perfect graph theorem.Glossary of graph theory terms_item_15_257
• 2.  A split of an arbitrary graph is a partition of its vertices into two nonempty subsets, such that the edges spanning this cut form a complete bipartite subgraph. The splits of a graph can be represented by a tree structure called its split decomposition. A split is called a strong split when it is not crossed by any other split. A split is called nontrivial when both of its sides have more than one vertex. A graph is called prime when it has no nontrivial splits.Glossary of graph theory terms_item_15_258
• square: 1.  The square of a graph G is the graph power G; in the other direction, G is the square root of G. The half-square of a bipartite graph is the subgraph of its square induced by one side of the bipartition.Glossary of graph theory terms_item_15_259
• 2.  A squaregraph is a planar graph that can be drawn so that all bounded faces are 4-cycles and all vertices of degree ≤ 3 belong to the outer face.Glossary of graph theory terms_item_15_260
• 3.  A square grid graph is a lattice graph defined from points in the plane with integer coordinates connected by unit-length edges.Glossary of graph theory terms_item_15_261
• stable: A stable set is a synonym for an independent set.Glossary of graph theory terms_item_15_262
• star: A star is a tree with one internal vertex; equivalently, it is a complete bipartite graph K1,n for some n ≥ 2. The special case of a star with three leaves is called a claw.Glossary of graph theory terms_item_15_263
• strength: The strength of a graph is the minimum ratio of the number of edges removed from the graph to components created, over all possible removals; it is analogous to toughness, based on vertex removals.Glossary of graph theory terms_item_15_264
• strong: 1.  For strong connectivity and strongly connected components of directed graphs, see connected and component. A strong orientation is an orientation that is strongly connected; see orientation.Glossary of graph theory terms_item_15_265
• 2.  For the strong perfect graph theorem, see perfect.Glossary of graph theory terms_item_15_266
• 3.  A strongly regular graph is a regular graph in which every two adjacent vertices have the same number of shared neighbours and every two non-adjacent vertices have the same number of shared neighbours.Glossary of graph theory terms_item_15_267
• 4.  A strongly chordal graph is a chordal graph in which every even cycle of length six or more has an odd chord.Glossary of graph theory terms_item_15_268
• 5.  A strongly perfect graph is a graph in which every induced subgraph has an independent set meeting all maximal cliques. The Meyniel graphs are also called "very strongly perfect graphs" because in them, every vertex belongs to such an independent set.Glossary of graph theory terms_item_15_269
• subforest: A subgraph of a forest.Glossary of graph theory terms_item_15_270
• subgraph: A subgraph of a graph G is another graph formed from a subset of the vertices and edges of G. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset.Glossary of graph theory terms_item_15_271
• subtree: A subtree is a connected subgraph of a tree. Sometimes, for rooted trees, subtrees are defined to be a special type of connected subgraph, formed by all vertices and edges reachable from a chosen vertex.Glossary of graph theory terms_item_15_272
• successor: A vertex coming after a given vertex in a directed path.Glossary of graph theory terms_item_15_273
• superconcentrator: A superconcentrator is a graph with two designated and equal-sized subsets of vertices I and O, such that for every two equal-sized subsets S of I and T O there exists a family of disjoint paths connecting every vertex in S to a vertex in T. Some sources require in addition that a superconcentrator be a directed acyclic graph, with I as its sources and O as its sinks.Glossary of graph theory terms_item_15_274
• supergraph: A graph formed by adding vertices, edges, or both to a given graph. If H is a subgraph of G, then G is a supergraph of H.Glossary of graph theory terms_item_15_275

## T Glossary of graph theory terms_section_19

Glossary of graph theory terms_description_list_16

• theta: 1.  A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.Glossary of graph theory terms_item_16_276
• 2.  The theta graph of a collection of points in the Euclidean plane is constructed by constructing a system of cones surrounding each point and adding one edge per cone, to the point whose projection onto a central ray of the cone is smallest.Glossary of graph theory terms_item_16_277
• 3.  The Lovász number or Lovász theta function of a graph is a graph invariant related to the clique number and chromatic number that can be computed in polynomial time by semidefinite programming.Glossary of graph theory terms_item_16_278
• topological: 1.  A topological graph is a representation of the vertices and edges of a graph by points and curves in the plane (not necessarily avoiding crossings).Glossary of graph theory terms_item_16_279
• 2.  Topological graph theory is the study of graph embeddings.Glossary of graph theory terms_item_16_280
• 3.  Topological sorting is the algorithmic problem of arranging a directed acyclic graph into a topological order, a vertex sequence such that each edge goes from an earlier vertex to a later vertex in the sequence.Glossary of graph theory terms_item_16_281
• totally disconnected: Synonym for edgeless.Glossary of graph theory terms_item_16_282
• tour: A closed trail, a walk that starts and ends at the same vertex and has no repeated edges. Euler tours are tours that use all of the graph edges; see Eulerian.Glossary of graph theory terms_item_16_283
• tournament: A tournament is an orientation of a complete graph; that is, it is a directed graph such that every two vertices are connected by exactly one directed edge (going in only one of the two directions between the two vertices).Glossary of graph theory terms_item_16_284
• traceable: A traceable graph is a graph that contains a Hamiltonian path.Glossary of graph theory terms_item_16_285
• trail: A walk without repeated edges.Glossary of graph theory terms_item_16_286
• transitive: Having to do with the transitive property. The transitive closure of a given directed graph is a graph on the same vertex set that has an edge from one vertex to another whenever the original graph has a path connecting the same two vertices. A transitive reduction of a graph is a minimal graph having the same transitive closure; directed acyclc graphs have a unique transitive reduction. A transitive orientation is an orientation of a graph that is its own transitive closure; it exists only for comparability graphs.Glossary of graph theory terms_item_16_287
• transpose: The transpose graph of a given directed graph is a graph on the same vertices, with each edge reversed in direction. It may also be called the converse or reverse of the graph.Glossary of graph theory terms_item_16_288
• tree: 1.  A tree is an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices.Glossary of graph theory terms_item_16_289
• 2.  A k-tree is a graph formed by gluing (k + 1)-cliques together on shared k-cliques. A tree in the ordinary sense is a 1-tree according to this definition.Glossary of graph theory terms_item_16_290
• tree decomposition: A tree decomposition of a graph G is a tree whose nodes are labeled with sets of vertices of G; these sets are called bags. For each vertex v, the bags that contain v must induce a subtree of the tree, and for each edge uv there must exist a bag that contains both u and v. The width of a tree decomposition is one less than the maximum number of vertices in any of its bags; the treewidth of G is the minimum width of any tree decomposition of G.Glossary of graph theory terms_item_16_291
• treewidth: The treewidth of a graph G is the minimum width of a tree decomposition of G. It can also be defined in terms of the clique number of a chordal completion of G, the order of a haven of G, or the order of a bramble of G.Glossary of graph theory terms_item_16_292
• triangle: A cycle of length three in a graph. A triangle-free graph is an undirected graph that does not have any triangle subgraphs.Glossary of graph theory terms_item_16_293
• Turán: 1.  Pál TuránGlossary of graph theory terms_item_16_294
• 2.  A Turán graph is a balanced complete multipartite graph.Glossary of graph theory terms_item_16_295
• 3.  Turán's theorem states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.Glossary of graph theory terms_item_16_296
• 4.  Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph.Glossary of graph theory terms_item_16_297

## U Glossary of graph theory terms_section_20

Glossary of graph theory terms_description_list_17

• undirected: An undirected graph is a graph in which the two endpoints of each edge are not distinguished from each other. See also directed and mixed. In a mixed graph, an undirected edge is again one in which the endpoints are not distinguished from each other.Glossary of graph theory terms_item_17_298
• uniform: A hypergraph is k-uniform when all its edges have k endpoints, and uniform when it is k-uniform for some k. For instance, ordinary graphs are the same as 2-uniform hypergraphs.Glossary of graph theory terms_item_17_299
• universal: 1.  A universal graph is a graph that contains as subgraphs all graphs in a given family of graphs, or all graphs of a given size or order within a given family of graphs.Glossary of graph theory terms_item_17_300
• 2.  A universal vertex (also called an apex or dominating vertex) is a vertex that is adjacent to every other vertex in the graph. For instance, wheel graphs and connected threshold graphs always have a universal vertex.Glossary of graph theory terms_item_17_301
• 3.  In the logic of graphs, a vertex that is universally quantified in a formula may be called a universal vertex for that formula.Glossary of graph theory terms_item_17_302
• unweighted graph: A graph whose vertices and edges have not been assigned weights; the opposite of a weighted graph.Glossary of graph theory terms_item_17_303

## V Glossary of graph theory terms_section_21

Glossary of graph theory terms_description_list_18

• V: See vertex set.Glossary of graph theory terms_item_18_304
• valency: Synonym for degree.Glossary of graph theory terms_item_18_305
• vertex: A vertex (plural vertices) is (together with edges) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure.Glossary of graph theory terms_item_18_306
• separating set: A set of vertices whose removal disconnects the graph. A one-vertex cut is called an articulation point or cut vertex.Glossary of graph theory terms_item_18_307
• vertex set: The set of vertices of a given graph G, sometimes denoted by V(G).Glossary of graph theory terms_item_18_308
• vertices: See vertex.Glossary of graph theory terms_item_18_309
• Vizing: 1.  Vadim G. VizingGlossary of graph theory terms_item_18_310
• 2.  Vizing's theorem that the chromatic index is at most one more than the maximum degree.Glossary of graph theory terms_item_18_311
• 3.  Vizing's conjecture on the domination number of Cartesian products of graphs.Glossary of graph theory terms_item_18_312
• volume: The sum of the degrees of a set of vertices.Glossary of graph theory terms_item_18_313

## W Glossary of graph theory terms_section_22

Glossary of graph theory terms_description_list_19

• W: The letter W is used in notation for wheel graphs and windmill graphs. The notation is not standardized.Glossary of graph theory terms_item_19_314
• Wagner: 1.  Klaus WagnerGlossary of graph theory terms_item_19_315
• 2.  The Wagner graph, an eight-vertex Möbius ladder.Glossary of graph theory terms_item_19_316
• 3.  Wagner's theorem characterizing planar graphs by their forbidden minors.Glossary of graph theory terms_item_19_317
• 4.  Wagner's theorem characterizing the K5-minor-free graphs.Glossary of graph theory terms_item_19_318
• walk: A walk is a finite or infinite sequence of edges which joins a sequence of vertices. Walks are also sometimes called chains. A walk is open if its first and last vertices are distinct, and closed if they are repeated.Glossary of graph theory terms_item_19_319
• weakly connected: A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.Glossary of graph theory terms_item_19_320
• weight: A numerical value, assigned as a label to a vertex or edge of a graph. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph.Glossary of graph theory terms_item_19_321
• weighted graph: A graph whose vertices or edges have been assigned weights; more specifically, a vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges.Glossary of graph theory terms_item_19_322
• well-colored: A well-colored graph is a graph all of whose greedy colorings use the same number of colors.Glossary of graph theory terms_item_19_323
• well-covered: A well-covered graph is a graph all of whose maximal independent sets are the same size.Glossary of graph theory terms_item_19_324
• wheel: A wheel graph is a graph formed by adding a universal vertex to a simple cycle.Glossary of graph theory terms_item_19_325
• width: 1.  A synonym for degeneracy.Glossary of graph theory terms_item_19_326
• 2.  For other graph invariants known as width, see bandwidth, branchwidth, clique-width, pathwidth, and treewidth.Glossary of graph theory terms_item_19_327
• 3.  The width of a tree decomposition or path decomposition is one less than the maximum size of one of its bags, and may be used to define treewidth and pathwidth.Glossary of graph theory terms_item_19_328
• 4.  The width of a directed acyclic graph is the maximal cardinality of an antichain.Glossary of graph theory terms_item_19_329
• windmill: A windmill graph is the union of a collection of cliques, all of the same order as each other, with one shared vertex belonging to all the cliques and all other vertices and edges distinct.Glossary of graph theory terms_item_19_330