Glossary of graph theory

One major problem that has plagued graph theory since its inception isthe consistent lack of consistency in terminology. This page will try to keep current with some of the latest trends, however,you can be assured that some people will always use some different notations or the same term with different meanings.

While using this glossary of graph theory, please keep in mind that it is merely a starting point forbeginners to get familiar with some basic concepts and terminologies, and is by no means a definitive presentation of what thoseconcepts and terminolgies ought to be.

Basics

A graph G is consisted of two types of elements, namely vertex and edge, and can be modeled as a set system of 2-element sets (edges) over a ground set (vertices).

A vertex (basic element) is simply drawn as a node or a dot. The vertexset of G is usually denoted by V(G), or V when there is no danger of confusion. Theorder of a graph is the number of its vertices, i.e. |V(G)|.

An edge (a set of two elements) is drawn as a line connecting two vertices, calledendvertices, or endpoints. An edge with endvertices x and y is denoted by xywithout any mid-dot in between, that is, do not write x⋅y. The edge set ofG is usually denoted by E(G), or E when there is no danger of confusion. Thesize of a graph is the number of its edges, i.e. |E(G)|.

A loop is an edge whose endvertices are the same vertex. An edge is multiple if there isanother edge with the same endvertices; otherwise it is simple. The multiplicity of an edge isthe number of multiple edges sharing the same endvertices; the multiplicity of a graph, the maximum multiplicityof its edges. A graph is a simple graph if it has no multiple edges or loops, a multigraph ifit has multiple edges, but no loops, and a pseudograph if it contains both multiple edges and loops. When statedwithout any qualification, a graph is almost always assumed to be simple.

A label may be used on either an edge or a vertex to either uniquely identify it or otherwise indicatemeaning. Graphs with labeled edges or vertices are known as labeled, those without asunlabeled. More specifically, graphs with labeled vertices only are vertex-labeled, those withlabeled edges only are edge-labeled.

The example graph pictured to the right is a simple graph with vertex set V = {1, 2, 3, 4, 5, 6} and edge setE = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (with the map w being the identity).

A hyperedge is an edge that is allowed to take on any number of vertices, even 2 or more. A graph that allowsany hyperedge is called a hypergraph . A simple graph can beconsidered a special case of the hypergraph, namely the 2-uniform hypergraph. However, when stated without any qualification, anedge is always assumed to be consisted of at most 2 vertices, and a graph is never confused with a hypergraph.

The complement of a graphG is a graph with the same vertex set as G but with an edge set such that xy is an edge in if and only if xy is not an edge inG.

An empty graph is a graph possibly with some vertices, but no edges.

The null graph is the graph with no vertices and no edges.

A graph is infinite if it has inifinitely many vertices or edges or both; otherwise the graph isfinite. When stated without any qualification, a graph is usually assumed to be finite.

Two graphs G and H are said to be isomorphic, denoted by G ~ H, if there is anone-to-one correpondence, called isomorphism, between the vertices of the graph such that two vertices areadjacent in G if and only if their corresponding vertices are adjacent in H. Likewise, a graph G issaid to be homomorphic to a graph H if there is a mapping, called homomorphism , from V(G) to V(H) such that if two vertices areadjacent in G then their corresponding vertices are adjacent in H.

Subgraph

A subgraph of a graph G is a graph whose vertex and edge sets are subsets of those of G. Onthe contrary, a supergraph of a graph G is a graph that contains G as a subgraph. We say agraph G contains another graph H if some subgraph of G is isomorphic toH.

A subgraph H is a spanning subgraph, or factor, of a graph G if it has the samevertex set as G. We say H spans G.

A subgraph H of a graph G is said to be induced if, for any pair of vertices x andy of H, xy is an edge of H if and only if xy is an edge of G. In other words, H isan induced subgraph of G if it has the most edges that appear in G over the same vertex set. If H ischosen based on a vertex subset S of V(G), then H can be written as G[S] and is saidto be induced by S.

A graph that does not contain H as an induced subgraph is said to be H-free.

A universal graph in a class K of graphs is a simple graph in which every element in K can be embbeded as asubgraph.

Path

Traditionally, a path is graph consisted of a sequenceof successively incident edges and their endvertices, where the terminating vertices are distinct. In modern literature, thisdefinition usually refers to what is known as a trail, or open walk. When stated without anyqualification, a path of n vertices, denoted by P_n, is usually assumed to be asimple path, or a simple trail in the modern sense, meaning every vertex is incident to at most twoedges.

Two paths are internally disjoint (some people consider it independent) if they do not have anyvertex in common, except the first and last ones.

The length of a path is the number of edges that the path uses. P_n has length n- 1. Some people count multiple edges multiple times. In the example graph, (1, 2, 5, 1, 2, 3) is a path with length 5, and (5,2, 1) is a simple path of length 2.

A spanning path is also called a Hamiltonianpath , or traceable path. A graph that contains a Hamiltonian path is a traceable graph;and one that, given any pair of (distinct) vertices, contains a Hamiltonian path using them as endvertices, a Hamiltonianconnected graph.

Cycle

Traditionally, a cycle in a graph consisted of asequence of successively incident edges and their endvertices, where the terminating vertices are identical. In modernliterature, this definition usually refers to what is known as a circuit, or closed walk. When statedwithout any qualification, a cycle of n vertices, denoted by C_n, is usually assumedto be a simple cycle, or a simple circuit in the modern sense, meaning every vertex is incident toexactly two edges. In the above graph (1, 5, 2, 1) is a simple cycle.

The length of a cycle is the number of its edges. C_n has length n. A cycle,unlike a path, is not allowed to have length 0. Cycles of length 1 are loops. Cycles of length 2 are pairs of multiple edges. Inthe example graph, (1, 2, 3, 4, 5, 2, 1) is a cycle of length 6.

A cycle that has odd length is an odd cycle; otherwise it is an even cycle. A graph can beproved bipartite if there do not exist any odd cycle. See complete bipartite graph

The girth of a graph is the length of a shortest (simple) cycle inthe graph; and the circumference, the length of a longest (simple) cycle. The girth and circumference of anacyclic graph are defined to be infinity ∞.

A graph is acyclic if it contains no cycles; unicyclic if it contains exactly one cycle; andpancyclic if it contains cycles of every possible length (from 3 to the order of the graph).

An Eulerian path in a graph is a path that uses eachedge precisely once. If such a path exists, the graph is called traversable. An Eulerian cycle is acycle which uses each edge precisely once.

The example graph does not contain an Eulerian path, but it does contain a Hamiltonian path.

C₃ is called a triangle.

A spanning cycle is also called a Hamiltoniancycle . A graph that contains a Hamiltonian cycle is a Hamiltonian graph.

Tree

A tree is a connected acyclic simplegraph. A vertex of degree 1 is called a leaf, or pendant vertex. An edge incident to a leaf is anleaf edge, or pendant edge. (Some people define a leaf edge as a leaf and then define aleaf vertex on top of it. These two sets of definitions are often used interchangeably.) A non-leaf vertex is aninternal vertex. Sometimes, one vertex of the tree is distinguished, and called the root. Arooted tree is a tree with a root. Rooted trees are often treated as directed acyclicgraphs with the edges pointing away from the root.

Trees are commonly used as data structures in computer science (see tree data structure ).

A forest is a vertex-disjoint union of trees; or, equivalently, an acyclic graph.

A subtree of the graph G is a subgraph that is a tree.

A spanning tree is a spanning subgraph that is a tree. Every graph has a spanning forest. But only aconnected graph has a spanning tree.

A special kind of tree called star is K_1,k. An induced star with 3 edges is aclaw.

A k-ary tree is a rooted tree in which every internal vertex has k children. An1-ary tree is just a path. A 2-ary tree is also called a binary tree.

Clique

The complete graph K_n of ordern is a simple graph with n vertices in which every vertex is adjacent to every other. The example graph is notcomplete. The complete graph on n vertices is often denoted by K_n. It has n(n-1)/2edges (corresponding to all possible choices of pairs of vertices).

A clique (pronounced "click") in a graph is a setof pairwise adjacent vertices. Since the subgraph induced by a clique is a complete subgraph, the two terms and their notationsare usually used interchangeably. A k-clique is a clique of order k. In the example graphabove, vertices 1, 2 and 5 form a 3-clique, or a triangle.

The clique number ω(G) of a graph G is the order of a largest clique inG.

Independence

In graph theory, the word independent usually carries the connotation of pairwise disjoint or mutuallynonadjacent. In this sense, independence is a form of immediate nonadjacency. An isolated vertexis a vertex not incident to any edges. An independent set, or stable set or staset, is a setof isolated vertices. Since the graph induced by any independent set is an empty graph, the two terms are usually usedinterchangeably. In the example above, vertices 1, 3, and 6 form an independent set; and 3, 5, and 6 form another one.

The independence number α(G) of a graph G is a the size of a largest independent setof G.

A graph can be decomposed into independent sets in the sense that the entire vertex set of the graph can bepartitioned into pairwise disjoint independent subsets. Such independent subsets are called partite sets, orsimply parts.

A graph that can be decomposed into two partite sets but not fewer is bipartite; three sets but not fewer,tripartite; k sets but not fewer, k-partite; and an unknown number of sets,multipartite. An 1-partite graph is the same as an independent set, or an empty graph. A 2-partite graph is thesame as a bipartite graph. A graph that can be decomposed into k partite sets is also said to be k-colorable .

The matching number α′(G) of a graph G is a the size of a largestmatching, or pairwise vertex disjoint edges, of G. A spanning matching is also called aperfect matching.

Degree

In graph theory, degree, especially that of a vertex, is usually a measure of immediate adjacency.

An edge connects two vertices; these two vertices are said to be incident to that edge, or, equivalently,that edge incident to those two vertices. All degree-related concepts have to do with adajacency or incidence.

The degree, or valency, d_G(v) of a vertex v in a graphG is the number of edges incident to v, with loops being counted twice. A vertex of degree 0 is an isolatedvertex. A vertex of degree 1 is a leaf. In the example graph vertices 1 and 3 have a degree of 2, vertices 2,4 and 5 have adegree of 3 and vertex 6 has a degree of 1. If E is finite, then the total sum of vertex degrees is equal to twice thenumber of edges.

A degree sequence is a list of degrees of a graph in non-increasing order (e.g. d₁≥ d₂ ≥ … ≥ d_n). A sequence of non-increasing integers isrealizable if it is a degree sequence of some graph.

Two vertices u and v are considered adjacent if an edge exists between them. We denote byu ↓ v. In the above graph, vertices 1 and 2 are adjacent, but vertices 2 and 4 are not. The set ofneighbors , called a (open) neighborhood N_G(v) for a vertexv in a graph G, consists of all vertices adjacent to v but not including v. When vis also included, it is called a closed neighborhood, denoted by N_G[v]. When statedwithout any qualification, a neighborhood is assumed to be open. The subscript G is usually dropped when there is nodanger of confusion. In the example graph, vertex 1 has two neighbors: vertices 2 and 5. For a simple graph, the number ofneighbors that a vertex has coincides with its degree.

A dominating set of a graph is a vertex subset whose closed neighborhood include all vertice of the graph. Avertex v dominates another vertex u if there is an edge from v to u. Avertex subset V dominates another vertex subset U if every vertex in U is adjacent tosome vertex in V. The minimum size of a dominating set is the domination number γ(G).

In computers, a finite, directed or undirected graph (with n vertices, say) is often represented by its adjacency matrix : an n-by-n matrix whose entry in row i and columnj gives the number of edges from the i-th to the j-th vertex. A rich theory of the relationshipbetween the properties of this matrix and that of its graph is studied in spectral graph theory .

The maximum degree Δ(G) of a graph G is the largest degree over all vertices; theminimum degree δ(G), the smallest.

A graph in which every vertex has the same degree is regular . It is k-regular if every vertex has degree k. A0-regular graph is an independent set. A 1-regular graph is a matching. A 2-regular graph is a vertex disjoint union of cycles. A3-regular graph is said to be cubic, or trivalent.

A k-factor is a k-regular spanning subgraph. An 1-factor is a perfect matching. Apartition of edges of a graph into k-factors is called a k-factorization. Ak-factorable graph is a graph that admits a k-factorization.

A graph is biregular if it has unequal maximum and minimum degrees and every vertex has one of those twodegrees.

A strongly regular graph is a regular graph such that any adjacent vertices have the same number of commonneighbors as other adjacent pairs and that any nonadjacent vertice have the same number of common neighbors as other nonadajacentpairs.

A k-partite graph is semiregular if each of its partite set has a uniform degree;equipartite if each partite set has the same size; and balanced k-partite if eachpartite set differs in size by at most 1 with any other.

A complete multipartite graph is a graph in which vertices are adjacent if and only if they belong todifferent partite sets. A complete bipartitegraph is also referred to as a biclique.

Connectivity

Connectivity extends the concept of adjacency and is essentially a form (and measure) of concatenated adjacency.

If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to beconnected; otherwise, the graph is disconnected. A graph is totallydisconnected if there is no path connecting any pair of vertices. This is just another name to describe an empty graphor independent set.

A cut vertex, or articulation point, is a vertex whose removal disconnects a graph. A cutset, or vertex cut or separating set, is a set of vertices whose removal disconnects the graph.

If it is always possible to establish a path from any vertex to every other one even after removing any k - 1vertices, then the graph is said to be k-connected. Note that a graph is k-connected if andonly if it contains k internally disjoint paths between any two vertices. The example graph above is connected (andtherefore 1-connected), but not 2-connected. The connectivity κ(G) of a graph G is theminumum number of vertices needed to disconnect G. By convention, K_n has connectivity n -1; and a disconnected graph has connectivity 0.

A bridge, or cut edge or isthmus, is an edge whose removal disconnects a graph. Adisconnecting set is a set of edges whose removal increases the number of components. An edgecut is the set of all edges having one endvertex in some proper vertex subset S and another endvertex inV(G)\S. Edges of K₃ form a disconnecting set but not an edge cut. Any two edges ofK₃ form a minimal disconnecting set as well as an edge cut. An edge cut is necessarily a disconnecting set;and a minimal disconnecting set of an nonempty graph is necessarily an edge cut. A bond is a minimal (but notnecessarily minimum), nonempty set of edges whose removal disconnects a graph.

A graph is k-edge-connectedif any subgraph formed by removing any k - 1 edges is stillconnected. The edge connectivity κ′(G) of a graph G is the minumum number of edgesneeded to disconnect G. One well-known result is that κ(G) ≤ κ′(G) ≤δ(G).

A component is a maximally connected subgraph; a block, either a maximally 2-connectedsubgraph or a bridge with its endvertices; and a biconnected component, a maximal set of edges in which any twomembers lie on a common simple cycle.

Distance

In graph theory, distance, especially when it is unweighted, is usually a measure of concatenated adjacency.

The distance d_G(u, v) between two (not necessary distinct)vertices u and v in a graph G is the length of a shortest path between them. The subscript Gis usually dropped when there is no danger of confusion. When u and v are identitcal, their distance is 0. Whenu and v are unreachable from each other, their distance is defined to be infinity ∞.

The eccentricity ε_G(v) of a vertex v in a graph G is themaximum distance from v to any other vertex. The diameter diam(G) of a graph G is themaximum eccentricity over all vertices in a graph; and the radius rad(G), the minimum. When there aretwo components in G, diam(G) and rad(G) defined to be infinity ∞. By definition,diam(G) ≤ 2 rad(G). Vertices of minimum eccentricity form the center. A tree has at mosttwo center vertices.

The Wiener index of a vertex v in a graph G, denoted by W_G(v)is the sum of distances between v and all others. The Wiener index of a graph G, denoted byW(G), is the sum of distances over all pairs of vertices. An undirected graph's Wienerpolynomial is defined to be Σ q^d(u,v) over all unordered pairs ofvertices u and v. Wiener index and Wiener polynomial are of particular interests to mathematical chemists.

The k-th power G^k of a graph G is a supergraph formed by adding an edgebetween all pairs of vertices of G with distance at most k. A second power of a graph is also called asquare.

A k-spanner is a spanning subgraph in which every two vertices are at most k times as farapart on S than on G. The number k is the dilation. k-spanner is used for studying geometricnetwork optimization.

Genus

A crossing is a pair of intersecting edges. A graph is embeddable on a surface if itsvertices and edges can be arranged on it without any crossing. The genus of a graph is the lowest genus of any surface on which the graph can embed.

A planar graph is one which can be drawn onthe (Euclidean) plane without any crossing; and a plane graph, one which is drawn in such fashion. Inother words, a planar graph is a graph of genus 0. The example graph is planar; the complete graph on n vertices, forn> 4, is not planar. Also, a tree is necessarily a planar graph.

When a graph is drawn without any crossing, any cycle that surrounds a region without any edge reaching from the cycle insideto such region forms a face. Two faces on a plane graph are adjacent if they share a commonedge. A dual, or planar dual when the context needs to be clarified, G^* of a planegraph G is a graph whose vertices represent the faces, including any outerface, of G and are adjacent inG^* if and only if their corresponding faces are adjacent in G. The dual of a planar graph is alwaysa planar pseudograph (e.g. consider the dual of a triangle). In the familiar case of a 3-connected simple planar graphG (isomorphic to a convex polyhedron P), the dual G^* is also a 3-connected simple planargraph (and isomorphic to the dual polyhedron P^*).

Furthermore, since we can establish a sense of "inside" and "outside" on a plane, we can identify an "outermost" region thatcontains the entire graph if the graph does not cover the entire plane. Such outermost region is called an outerface. An outerplanar graph is one which can be drawn in the planar fashion such that itsvertices are all adjacent to the outer face; and an outerplane graph, one which is drawn in suchfashion.

The minimum number of crossings that must appear when a graph is drawn on a plane is called the crossingnumber.

The minimum number of planar graphs needed to cover a graph is the thickness of the graph.

Weight

A weighted graph associates a real number label(weight) with every edge in the graph. The weight of a path in a weighted graph is the sum ofthe weights of the traversed edges. Sometimes the word cost is used instead of weight. When stated without anyqualification, a graph is always assumed to be unweighted.

Direction

An arc, or directed edge, is an ordered pair of endvertices. In such ordered pair, the first vertexis called a head, or initial vertex; and the second one, a tail, or terminalvertex. It can be thought of as an edge associated with a direction, namely designating a head and a tail to theendvertices. An undirected edge disregards any sense of direction and treats both endvertices interchangeably. Aloop in a diagraph , however, keeps a sense of direction and treats both head and tail identically. A set ofarcs are multiple, or parallel, if they share the same head and the same tail. A pair of arcs areanti-parallel if one's head/tail is the other's tail/head. A digraph, or directed graph , is analogous to an undirected graph except that itcontains at least an arc. An oriented graph contains only arcs. When stated without any qualification, a graphis almost always assumed to be undirected. Also, a digraph is usually assumed to contain no undirected edges.

A digraph is called simple if it has no loops and at most one arc between any pair of vertices. When statedwithout any qualification, a digraph is usually assumed to be simple.

In a digraph Γ, we distinguish the out degree d_Γ⁺(v), thenumber of edges leaving a vertex v, and the in degreed_Γ^-(v), the number of edges entering a vertex v. The degreed_Γ(v) of a vertex v is equal to the sum of its out- and in- degrees. When the contextis clear, the subscript Γ can be dropped. Maximum and minimum out degrees are denoted by Δ⁺(Γ) andδ⁺(Γ); and maximum and minimum in degrees, Δ^-(Γ) and δ^-(Γ).

An out-neighborhood, or success set, N⁺_Γ(v) of a vertexv is the set of tails of arcs going from v. Likewise, an in-neighborhood, or predecessorset, N^-_Γ(v) of a vertex v is the set of heads of arc going intov.

A source is a vertex with 0 in-degree; and a sink, 0 out-degree.

A vertex v dominates another vertex u if there is an arc from v to u. Avertex subset S is out-dominating if every vertex not in S is dominated by some vertex inS; and in-dominating if every vertex in S is dominated by some vertex not in S.

A kernel is an independent out-dominating set. A digraph is kernel perfect if every inducedsub-digraph has a kernel.

An Eulerian digraph is a digraph with equal in- and out-degrees at every vertex.

An orientation is an assignment of directions to the edges of an undirected or partially directed graph. Whenstated without any qualification, it is usually assumed that all undirected edges are replaced by a directed one in anorientation. Also, the underlying graph is usually assumed to be undirected and simple.

A tournament is a digraph in which each pair of vertices is connected by exactly one arc. In other words, itis an oriented complete graph.

A directed path, or just a path when the context is clear, is an oriented simple path such that allarcs go the same direction, meaning all internal vertices have in- and out-degrees 1. A vertex u isreachable from another vertex v if there is a directed path that starts from u and ends atv. Note that in general the condition that u is reachable from v does not imply that v isalso reachable from u.

A digraph is strongly connected if every vertex is reachable from every other following the directions of thearcs. On the contrary, a diagraph is weakly connected if its underlying undirected graph is connected. A weaklyconnected graph can be thought of as a digraph in which every vertex is "reachable" from every other but not necessarilyfollowing the directions of the arcs. A strong orientation is an orientation that produces a strongly connecteddigraph.

A directed cycle, or just a cycle when the context is clear, is an oriented simple cycle such thatall arcs go the same direction, meaning all vertices have in- and out-degrees 1. A digraph is acyclic if it doesnot contain any directed cycle. A finite, acyclic digraph with no isolated vertices necessarily contain at least one source andat least one sink.

An arborescence, or out-tree or branching, is an oriented tree in which all vertices arereachable from a single vertex. Likewise, an in-tree is an oriented tree in which a single vertex is reachable fromevery other one.

See also

• Graph (mathematics)
• Graph theory
• List of graph theory topics

General references

• Bollobás, Béla (1998). Modern graph theory. New York:Springer-Verlag. ISBN 0-387-98488-7 [Packed with advanced topics followed by a historical overview at the end of each chapter.]
• West, Douglas B. (2001). Introduction to graph theory (2ed). Upper Saddle River: Prentice Hall. ISBN 0-13-014400-2 . [Tons ofillustrations, references, and exercises. The most complete introductory guide to the subject.]
• Eric W. Weisstein. "Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Graph.html