Glossary of graph theory

Look up Appendix:Glossary of graph theory in Wiktionary, the free dictionary.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

!$@

[]

G[S] is the induced subgraph of a graph G for vertex subset S.

′

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.

A

acyclic

A graph is acyclic if it has no cycles. An acyclic undirected graph is the same thing as a forest. Acyclic directed graphs are more often called directed acyclic graphs.

adjacency matrix

The adjacency matrix of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row i and column j when vertices i and j are adjacent, and a zero otherwise.

adjacent

The relation between two vertices that are both endpoints of the same edge.

α

For a graph G, α(G) is its independence number (see independent), and α′(G) is its matching number (see matching).

alternating

In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated vertices. A larger matching can be found as the symmetric difference of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.

anti-edge

Synonym for non-edge, a pair of non-adjacent vertices.

anti-triangle

A three-vertex independent set, the complement of a triangle.

arborescence

Synonym for a rooted and directed tree; see tree.

arc

An edge of a directed graph, also sometimes called an arrow.

arrow

Synonym for arc, a directed edge, used especially in the context of quivers.

articulation

An articulation point or cut vertex is a vertex whose removal would disconnect the graph.

-ary

A k-ary tree is a rooted tree in which every internal vertex has no more than k children. A 1-ary tree is just a path. A 2-ary tree is also called a binary tree, although that term more properly refers to 2-ary trees in which the children of each node are distinguished as being left or right children (with at most one of each type).

augmenting

A special type of alternating path; see alternating.

automorphism

A graph automorphism is a symmetry of a graph, an isomorphism from the graph to itself.

B

bipartite

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.

biregular

A biregular graph is one in which there are only two different vertex degrees.

block

1.  A block or biconnected component is a maximal subgraph in which every two vertices or edges belong to a simple cycle. It may be a 2-vertex-connected subgraph, a bridge edge, or an isolated vertex. In a connected graph, the collection of blocks and the articulation points separating them form the vertices of a tree, the block-cut tree, whose edges connect blocks to the articulation points within those blocks. The block graph of a graph is another graph whose vertices are the blocks, with an edge connecting two vertices when the correspondiing blocks share an articulation point.

2.  A block graph (also called a clique tree, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete. The block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.

bond

A minimal cut-set: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.

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.

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.

C

C

C_n is an n-vertex cycle graph; see cycle.

cactus

A cactus graph, cactus tree, cactus, or Husimi tree is a connected graph in which each edge belongs to at most one cycle. Its blocks are cycles or single edges. If, in addition, each vertex belongs to at most two blocks, then it is called a Christmas cactus.

caterpillar

A caterpillar tree or caterpillar is a tree in which the internal nodes induce a path.

center

The center of a graph is the set of vertices of minimum eccentricity.

chain

1.  Synonym for walk.

2.  When applying methods from algebraic topology to graphs, an element of a chain complex, namely a set of vertices or a set of edges.

child

In a rooted tree, a child of a vertex v is a neighbour of v along an outgoing edge, one that is directed away from the root.

chord, chordal

A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle. A chordal graph is a graph in which every cycle of four or more vertices has a chord, so the only induced cycles are triangles. A chordal bipartite graph is not chordal (unless it is a forest); it is a bipartite graph in which every cycle of six or more vertices has a chord, so the only induced cycles are 4-cycles.

circuit

A circuit may refer to a simple cycle, a trail (a closed tour without repeated edges), or an element of the cycle space (an Eulerian spanning subgraph). The circuit rank of a graph is the dimension of its cycle space.

circumference

The circumference of a graph is the length of its longest simple cycle. The graph is Hamiltonian if and only if its circumference equals its order.

claw

A claw is a tree with one internal vertex and three leaves, or equivalently the complete bipartite graph K_1,3. A claw-free graph is a graph that does not have an induced subgraph that is a claw.

clique

A clique is usually a complete subgraph, but some sources define it as a maximal complete subgraph, one that is not part of any larger complete subgraph. A k-clique is a clique of order k. The clique number κ(G) of a graph G is the order of its largest clique.

clique tree

A synonym for a block graph.

closed

1.  A closed neighbourhood is one that includes its central vertex; see neighbourhood.

2.  A closed walk is one that starts and ends at the same vertex; see walk.

3.  A graph is transitively closed if it equals its own transitive closure; see transitive.

comparability

An undirected graph is a comparability graph if its vertices are the elements of a partially ordered set and two vertices are adjacent when they are comparable in the partial order. Equivalently, a comparability graph is a graph that has a transitive orientation. Many other classes of graphs can be defined as the comparability graphs of special types of partial order.

complement

The complement graph of a simple graph G is another graph on the same vertex set as G, with an edge for each two vertices that are not adjacent in G.

complete

1.  A complete graph is one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with n vertices is often denoted K_n. A complete bipartite graph is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with a vertices on one side of the partition and b vertices on the other side is often denoted K_a,b. The same terminology and notation has also been extended to complete multipartite graphs, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are a, b, c, ... then this graph is denoted K_{a, b, c, ...}.

2.  A completion of a given graph is a supergraph that has some desired property. For instance, a chordal completion is a supergraph that is a chordal graph.

3.  A complete matching is a synonym for a perfect matching; see matching.

component

A connected component of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have some higher order of connectivity, including biconnected components, triconnected components, and strongly connected components.

connected

A connected graph is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), k-vertex-connected graphs (removing fewer than k vertices cannot disconnect the graph), and k-edge-connected graphs (removing fewer than k edges cannot disconnect the graph).

converse

The converse graph is a synonym for the transpose graph; see transpose.

cover

A vertex cover is a set of vertices incident to every edge in a graph. An edge cover is a set of edges incident to every vertex in a graph.

critical

A critical graph for a given property is one in which the property would change for every subgraph formed by deleting a single vertex. For instance, a factor-critical graph is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself.

cut

A cut is a partition of the vertices into two subsets. An edge is said to span the cut if it has endpoints in both subsets, and a cut-set is the set of edges that span a cut. Thus, the removal of the cut-set disconnects the graph. A bond is a minimal cut-set. A minimum cut is a cut whose cut-set has minimum total weight, possibly restricted to cuts that separate a designated pair of vertces; they are characterized by the max-flow min-cut theorem.The cut space of a graph is a vector space having the cut-sets of the graph as its elements. An edge cut, more generally, is a set of edges whose removal disconnects the graph, and similarly a vertex cut or separating set is a set of vertices whose removal disconnects the graph. A one-edge cut is called a bridge, isthmus, or cut edge (see bridge). A one-vertex cut is called an articulation point or cut vertex (see articulation point).

cycle

A cycle may either refer to a closed walk (also called a tour) or more specifically to a closed walk without repeated vertices or edges (a simple cycle). In either case, the choice of starting vertex is usually considered unimportant: cyclic permutations of the walk produce the same cycle. Important special cases of cycles include Hamiltonian cycles, induced cycles, peripheral cycles, and the shortest cycle, which defines the girth of a graph. A k-cycle is a cycle of length k; for instance a 2-cycle is a digon and a 3-cycle is a triangle. A cycle graph is a graph that is itself a simple cycle; a cycle graph with n vertices is commonly denoted C_n. The cycle space is a vector space generated by simple cycles in a graph.

D

degree

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 d_G(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).

Δ, δ

Δ(G) is the maximum degree of a vertex in G, and δ(G) is the minimum degree; see degree.

diameter

The diameter of a graph is the maximum pairwise distance between any two of its vertices.

diamond

The diamond graph is an undirected graph with four vertices and five edges.

digon

A simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in simple undirected graphs, as forming a closed walk by repeating the same edge twice does not produce a simple cycle.

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.

disjoint

1.  Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.

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.

distance

The distance between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.

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.

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 unversal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.

E

E

E(G) is the edge set of G; see edge set.

eccentricity

The eccentricity of a vertex is the farthest distance from it to any other vertex.

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.

edge set

The set of vertices of a given graph G, sometimes denoted by E(G).

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.

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.

empty graph

1.  An edgeless graph on a set of vertices.

2.  The graph with no vertices and no edges.

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.

endpoint

One of the two vertices incident to a given edge, or one of the two vertices at the start and end of a walk or path.

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.

F

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.

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.

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 the same thing as an edge coloring.

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.

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.

forbidden

A forbidden graph characterization is a characterization of a set 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.

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.

full

Synonym for induced.

G

G

A variable often used to denote a graph.

genus

The genus of a graph is the minimum genus of a surface onto which it can be embedded; see embedding.

geodesic

Synonym for a shortest path.

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.

girth

The girth of a graph is the length of its shortest cycle.

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.

H

H

A variable often used to denote a graph, especially when another graph has already been denoted by G.

H-coloring

An H-coloring of a graph G (where H is also a graph) is a homomorphism from H to G.

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 set of all graphs (or, often, all finite graphs) that are H-free.^[1] For instance the triangle-free graphs are the graphs that do not have a triangle graph as a subgraph.

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 Hamiiltonian cycle.

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.

homomorphic equivalence

Two graphs are homomorphically equivalent if there exist two homomorphisms, one from each graph to the other graph.

homomorphism

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.

hyperedge

An edge in a hypergraph, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.

hypercube

A hypercube graph is a graph formed from the vertices and edges of a geometric hypercube.

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.

I

in-degree

The number of incoming edges in a directed graph; see degree.

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.

incident

The relation between an edge and one of its endpoints.

incomparability

An incomparability graph is the complement of a comparability graph; see comparability.

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.

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.

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.

infinite

An infinite graph is one that is not finite; see finite.

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.

isolated

An isolated vertex of a graph is a vertex whose degree is zero, that is, a vertex with no incident edges.

isomorphic

Two graphs are isomorphic if there is an isomorphism between them; see isomorphism.

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.

isthmus

See bridge.

K

K

For the notation for complete graphs, complete bipartite graphs, and complete multipartite graphs, see complete.

κ

κ(G) is the size of the maximum clique in G; see clique.

L

L

L(G) is the line graph of G; see line.

label

Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. A graph in which the vertices and edges are indistinguishable from each other is called unlabeled. 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.

leaf

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.

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.

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.

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 neighbourhoods are finite.

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.

M

matching

A matching is a set of edges no two of which share any endpoints. 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.

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.

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.

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.

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.

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 subdvision of H.

mixed

A mixed graph is a graph that may include both directed and undirected edges.

multigraph

A multigraph is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.

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.

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.

N

N

For the notation for open and closed neighbourhoods, see neighbourhood.

neighbour

A vertex that is adjacent to a given vertex.

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 neighbourhood of v in G may be denoted N_G(v) or N(v), and the closed neighbourhood may be denoted N_G[v] or N[v]. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.

non-edge

A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.

null graph

See empty graph.

O

odd

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. 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.

open

1.  See neighbourhood.

2.  See walk.

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.

2.  A type of logic of graphs; see first order and second order.

orientation, oriented

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.

out-degree

See degree.

outer

See face.

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.

P

path

A path may either be a walk (a sequence of vertices and edges, with both endpoints of an edge appearing adjacent to it in the sequence) or a simple path (a walk with no repetitions of vertices or edges), depending on the source. Important special cases include induced paths and shortest paths.

pendant

See leaf.

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.

2.  See matching.

peripheral

1.  A peripheral cycle or non-separating cycle is a cycle with at most one bridge.

2.  A peripheral vertex is a vertex whose eccentricity is maximum. In a tree, this must be a leaf.

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.

polytree

A polytree is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.

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.

pseudograph

A pseudograph is a graph or multigraph that allows self-loops.

proper

A proper subgraph is a subgraph that does not equal the whole graph.

Q

quiver

A quiver is a directed multigraph, as used in category theory. The edges of a quiver are called arrows.

R

radius

The radius of a graph is the maximum eccentricity of any vertex.

ray

A ray, in an infinite graph, is an infinite simple path with exactly one endpoint. The ends of a graph are equivalence classes of rays.

regular

A graph is d-regular when all of its vertices have degree d. A regular graph is a graph that is d-regular for some d.

reverse

See transpose.

root

A designated vertex in a graph, particularly in directed trees and rooted graphs.

S

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.

saturated

See matching.

self-loop

Synonym for loop.

simple

1.  A simple graph is a graph with no loops and with no 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.

2.  A simple path or a simple cycle is a path or cycle that has no repeated vertices (and no repeated edges).

sink

A sink, in a directed graph, is a vertex with no outgoing edges.

size

The size of a graph G is the number of its edges, |E(G)|.^[2] The variable m is often used for this quantity. See also order, the number of vertices.

source

A source, in a directed graph, is a vertex with no incoming edges.

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.

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.

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.

star

A star is a tree with one internal vertex; equivalently, it is a complete bipartite graph K_1,n for some n ≥ 2. The special case of a star with three leaves is called a claw.

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.

2.  For the strong perfect graph theorem, see perfect.

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.

subforest

A subgraph of a forest.

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.

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.

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.

T

theta

1.  A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.^[3]

2.  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.

totally disconnected

Synonym for edgeless.

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.

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).

trail

A walk without repeated edges.

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.

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.

tree

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.

triangle

A cycle of length three in a graph. A triangle-free graph is an undirected graph that does not have any triangle subgraphs.

U

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.

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.

universal

1.  A universal graph is a graph that contains as subgraphs all graphs in a given set of graphs, or all graphs of a given size or order within a given set of graphs.

2.  A universal vertex (also called a 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.

V

V

See vertex set.

valency

Synonym for degree.

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.

vertex set

The set of vertices of a given graph G, sometimes denoted by V(G).

vertices

See vertex.

W

walk

A walk is an alternating sequence of vertices and edges, starting and ending at a vertex, in which each edge is adjacent in the sequence to its two endpoints. In a directed graph the ordering of the endpoints of each edge in the sequence must be consistent with the direction of the edge. Some sources call walks paths, while others reserve the term "path" for a simple path (a walk without repeated vertices or edges). Walks are also sometimes called chains.^[4] A walk is open if its starts and ends at two different vertices, and closed if it starts and ends at the same vertex. A closed walk may also be called a cycle. Alternatively, the word "cycle" may be reserved for a simple closed walk (one without repeated vertices or edges except for the repetition of the starting and final vertex). A walk without repeated edges (but with vertex repetition allowed) may be called a trail and a closed trail may be called a tour.

wheel

A wheel graph is a graph formed by adding a universal vertex to a simple cycle.

References