Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage. A labeled graph with 6 vertices and 7 edges. ...
## Basics
A **graph** *G* consists of two types of elements, namely *vertices* and *edges*. Every edge has two *endpoints* in the set of vertices, and is said to **connect** or **join** the two endpoints. The set of edges can thus be defined as a subset of the family of all two-element sets of vertices. Often, however, the set of vertices is considered as a set, and there is an **incidence relation** which maps each edge to the pair of vertices that are its endpoints. Edges may be endowed with direction, leading to the notion of a **directed graph** or a digraph, see Section Direction. This article just presents the basic definitions. ...
Alternative models of *graph* exist; e.g., a graph may be thought as a Boolean binary function over the set of vertices or as a square (0,1)-matrix. The adjective Boolean (sometimes boolean), coined in honor of George Boole, is used in many contexts: An evaluation that results in either TRUE or FALSE. A boolean value is a truth value, either true or false, often coded 1 and 0, respectively. ...
In mathematics, a binary function, or function of two variables, is like a function, except that it has two inputs instead of one. ...
In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...
A **vertex** (basic element) is simply drawn as a *node* or a *dot*. The **vertex set** of *G* is usually denoted by *V*(*G*), or *V* when there is no danger of confusion. The **order** 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, called **endvertices**, or *endpoints*. An edge with endvertices *x* and *y* is denoted by *xy* without any symbol in between, so, do not write *x*⋅*y*. The **edge set** of *G* is usually denoted by *E*(*G*), or *E* when there is no danger of confusion. The **size** of a graph is the number of its edges, i.e. |*E*(*G*)|. A **loop** is an edge whose endvertices are the same vertex. A **link** has two distinct endvertices. An edge is **multiple** if there is another edge with the same endvertices; otherwise it is **simple**. The **multiplicity of an edge** is the number of multiple edges sharing the same endvertices; the **multiplicity of a graph**, the maximum multiplicity of its edges. A graph is a **simple graph** if it has no multiple edges or loops, a **multigraph** if it has multiple edges, but no loops, and a **multigraph** or **pseudograph** if it contains both multiple edges and loops (the literature is highly inconsistent). When stated without any qualification, a graph is almost always assumed to be simple—or one has to judge from the context.
**Graph labeling** usually refers to the assignment of unique labels (usually natural numbers) to the edges and vertices of a graph. Graphs with labeled edges or vertices are known as **labeled**, those without as **unlabeled**. More specifically, graphs with labeled vertices only are **vertex-labeled**, those with labeled edges only are **edge-labeled**. (This usage is to distinguish between graphs with identifiable vertex or edge sets on the one hand, and isomorphism types or classes of graphs on the other.) In the mathematical discipline of graph theory, a graph labeling is the assignment of unique identifiers to the edges and vertices of a graph. ...
Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...
A labelled simple graph with vertex set *V* = {1, 2, 3, 4, 5, 6} and edge set *E* = {{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, possibly more than 2. A graph that allows any hyperedge is called a **hypergraph**. A simple graph can be considered a special case of the hypergraph, namely the 2-uniform hypergraph. However, when stated without any qualification, an edge is always assumed to consist of at most 2 vertices, and a graph is never confused with a hypergraph. Image File history File links 6n-graf. ...
In mathematics, a hypergraph is a generalization of a graph, where edges can connect any number of vertices. ...
An **anti-edge** is an edge that "is not there". More formally, for two vertices *u* and *v*, {*u*,*v*} is an **anti-edge** in a graph *G* if (*u*,*v*) is not an edge in *G*. This means that there is either no edge between the two vertices or there is only an edge (*v*,*u*) from *v* to *u* if *G* is directed. An **anti-triangle** is a set of three vertices none of which are connected. The **complement** of a graph *G* 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 in *G*. An **edgeless graph** or **empty graph** is a graph possibly with some vertices, but no edges. Or, it is a graph with no vertices and no edges. The **null graph** is the graph with no vertices and no edges. Or, it is a graph with no edges and any number *n* of vertices, in which case it may be called the **null graph on ***n* vertices. (There is no consistency at all in the literature.) A graph is **infinite** if it has infinitely many vertices or edges or both; otherwise the graph is **finite**. An infinite graph where every vertex has finite degree is called **locally finite**. 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 a one-to-one correspondence, called an **isomorphism**, between the vertices of the graph such that two vertices are adjacent in *G* if and only if their corresponding vertices are adjacent in *H*. Likewise, a graph *G* is said to be **homomorphic** to a graph *H* if there is a mapping, called a **homomorphism**, from *V*(*G*) to *V*(*H*) such that if two vertices are adjacent in *G* then their corresponding vertices are adjacent in *H*. In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ...
### Subgraphs A **subgraph** of a graph *G* is a graph whose vertex and edge sets are subsets of those of *G*. In the other direction, a **supergraph** of a graph *G* is a graph that contains *G* as a subgraph. We say a graph *G* **contains** another graph *H* if some subgraph of *G* is *H* or is isomorphic to *H* (depending on the needs of the situation). A subgraph *H* is a **spanning subgraph**, or *factor*, of a graph *G* if it has the same vertex 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* and *y* of H, *xy* is an edge of *H* if and only if *xy* is an edge of G. In other words, *H* is an induced subgraph of *G* if it has the most edges that appear in *G* over the same vertex set. If *H* is chosen based on a vertex subset *S* of *V(G)*, then *H* can be written as *G*[*S*] and is said to 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 embedded as a subgraph.
### Walks A **walk** is an alternating sequence of vertices and edges, beginning and ending with a vertex, in which each vertex is incident to the two edges that precede and follow it in the sequence, and the vertices that precede and follow an edge are the endvertices of that edge. A walk is **closed** if its first and last vertices are the same, and **open** if they are different. The **length** *l* of a walk is the number of edges that it uses. For an open walk, *l* = *n*–1, where *n* is the number of vertices visited. For a closed walk, *l* = *n* (the start/end vertex is listed twice, but is not counted twice). In the example graph, (1, 2, 5, 1, 2, 3) is an open walk with length 5, and (4, 5, 2, 1, 5, 4) is a closed walk of length 5. A **trail** is a walk in which all the edges are distinct. A closed trail has been called a **tour** or **circuit**, but these are not universal, and the latter is often reserved for a regular subgraph of degree two. Traditionally, a **path** referred to what is now usually known as an *open walk*. Nowadays, when stated without any qualification, a path is usually defined to be **simple**, meaning that every vertex is incident to at most two edges. (The term **chain** has also been used to refer to a walk in which all vertices (and edges) are distinct.) In the example graph, (5, 2, 1) is a path of length 2. The closed equivalent to this type of walk is called a **cycle**. Like *path*, this term traditionally referred to any closed walk, but now is usually understood to be simple by definition. In the example graph, (1, 5, 2, 1) is a cycle of length 3. (A cycle, unlike a path, is not allowed to have length 0.) Paths and cycles of *n* vertices are often denoted by *P*_{n} and *C*_{n}, respectively. (Some authors use the length instead of the number of vertices, however.) In mathematics, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. ...
Cycle in graph theory and computer science has several meanings: A closed walk, with repeated vertices allowed. ...
A cycle that has odd length is an **odd cycle**; otherwise it is an **even cycle**. One theorem is that a graph is bipartite if and only if there does not exist any odd cycle. (See complete bipartite graph.) In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets with two vertices of the same set never sharing an edge. ...
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...
The **girth** of a graph is the length of a shortest (simple) cycle in the graph; and the **circumference**, the length of a longest (simple) cycle. The girth and circumference of an acyclic graph are defined to be infinity ∞. Girth generally refers to the circumference of a cylindrical object, such as a tree trunk. ...
The infinity symbol âˆž in several typefaces The word infinity comes from the Latin infinitas or unboundedness. ...
A graph is **acyclic** if it contains no cycles; **unicyclic** if it contains exactly one cycle; and **pancyclic** if it contains cycles of every possible length (from 3 to the order of the graph).
*C*_{1} is a **loop**, *C*_{2} is a pair of **digons** (multiple edges), and *C*_{3} is called a **triangle**. A path or cycle is **Hamiltonian** (or *spanning*) if it uses all vertices exactly once. A graph that contains a Hamiltonian path is **traceable**; and one that contains a Hamiltonian path for any given pair of (distinct) endvertices is a **Hamiltonian connected graph**. A graph that contains a Hamiltonian cycle is a **Hamiltonian graph**. In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ...
A trail or circuit (or cycle) is **Eulerian** if it uses all edges precisely once. A graph that contains an Eulerian trail is **traversable**. A graph that contains an Eulerian circuit is an **Eulerian graph**. The KÃ¶nigsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ...
The example graph does not contain an Eulerian trail, but it does contain a Hamiltonian path. 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. A **theta graph** is the union of three internally disjoint (simple) paths that have the same two distinct endvertices. A **theta**_{0} graph has seven vertices which can be arranged as the vertices of a regular hexagon plus an additional vertex in the center. The eight edges are the perimeter of the hexagon plus one diameter.
### Trees A **tree** is a connected acyclic simple graph. A vertex of degree 1 is called a **leaf**, or *pendant vertex*. An edge incident to a leaf is a **leaf edge**, or *pendant edge*. (Some people define a leaf edge as a *leaf* and then define a *leaf vertex* on top of it. These two sets of definitions are often used interchangeably.) A non-leaf vertex is an **internal vertex**. Sometimes, one vertex of the tree is distinguished, and called the **root**. A **rooted tree** is a tree with a root. **Rooted trees** are often treated as **directed acyclic graphs** with the edges pointing away from the root. A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
Trees are commonly used as data structures in computer science (see tree data structure). A binary tree, a simple type of branching linked data structure. ...
In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...
A **subtree** of the tree *T* is a subgraph of *T*. A **forest** is an acyclic simple graph. A **subforest** of the forest *F* is a subgraph of *F*. A **spanning tree** is a spanning subgraph that is a tree. Every graph has a spanning forest. But only a connected graph has a spanning tree. A spanning tree (red) of a graph (black), superimposed In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree which includes every vertex of that graph. ...
A special kind of tree called a **star** is *K*_{1,k}. An induced star with 3 edges is a **claw**. A *k*-ary tree is a rooted tree in which every internal vertex has *k* *children*. An 1-ary tree is just a path. A 2-ary tree is also called a **binary tree**.
### Cliques The **complete graph** *K*_{n} of order *n* is a simple graph with *n* vertices in which every vertex is adjacent to every other. The example graph is not complete. The complete graph on *n* vertices is often denoted by *K*_{n}. It has *n*(*n*-1)/2 edges (corresponding to all possible choices of pairs of vertices). In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...
A **clique** (pronounced "cleek") in a graph is a set of pairwise adjacent vertices. Since any subgraph induced by a clique is a complete subgraph, the two terms and their notations are usually used interchangeably. A *k*-clique is a clique of order *k*. In the example graph above, vertices 1, 2 and 5 form a 3-clique, or a *triangle*. K5, a complete graph. ...
The **clique number** ω(*G*) of a graph *G* is the order of a largest clique in *G*.
### Strongly connected component A related but weaker concept is that of a *strongly connected component*. Informally, a strongly connected component of a directed graph is a subgraph where all nodes in the subgraph are reachable by all other nodes in the subgraph. Reachability between nodes is established by the existence of a *path* between the nodes. A directed graph can be decomposed into strongly connected components by running the Depth-first search (DFS) algorithm twice: first, on the graph itself and next on the *transpose* of the graph in decreasing order of the finishing times of the first DFS. Given a directed graph G, the transpose G_{T} is the graph G with all the edge directions reversed. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...
### Knots A **knot** in a directed graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot have other vertices in the knot as destinations. Thus it is impossible to leave the knot while following the directions of the edges. If a general resource graph is expedient, then a knot is a sufficient condition for deadlock. A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. ...
### Minors A *minor* *G*_{2} = (*V*_{2},*E*_{2}) of *G*_{1} = (*V*_{1},*E*_{1}) is an injection from *V*_{2} to *V*_{1} such that every edge in *E*_{2} corresponds to a path (disjoint from all other such paths) in *G*_{1} such that every vertex in *V*_{1} is in one or more paths, or is part of the injection from *V*_{1} to *V*_{2}. This can alternatively be phrased in terms of *contractions*, which are operations which collapse a path and all vertices on it into a single edge (see Minor (graph theory)). In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ...
In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...
In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ...
### Embedding An *embedding* *G*_{1} = (*V*_{1},*E*_{1}) of *G*_{2} = (*V*_{2},*E*_{2}) is an injection from *V*_{2} to *V*_{1} such that every edge in *E*_{2} corresponds to a path (disjoint from all other such paths) in *G*_{1}. In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...
## Adjacency and 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 adjacency or incidence. The **degree**, or *valency*, *d*_{G}(*v*) of a vertex *v* in a graph *G* is the number of edges incident to *v*, with loops being counted twice. A vertex of degree 0 is an isolated vertex. 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 a degree 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 the number of edges. In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex. ...
A **degree sequence** is a list of degrees of a graph in non-increasing order (e.g. *d*_{1} ≥ *d*_{2} ≥ … ≥ *d*_{n}). A sequence of non-increasing integers is **realizable** 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 this by *u* ↓ *v*. In the above graph, vertices 1 and 2 are adjacent, but vertices 2 and 4 are not. The set of **neighbors** of *v*, that is, vertices adjacent to *v* not including *v* itself, forms an induced subgraph called the **(open) neighborhood** of *v* and denoted *N*_{G}(*v*). When *v* is also included, it is called a **closed neighborhood** and denoted by *N*_{G}[*v*]. When stated without any qualification, a neighborhood is assumed to be open. The subscript *G* is usually dropped when there is no danger of confusion; the same neighborhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. In the example graph, vertex 1 has two neighbors: vertices 2 and 5. For a simple graph, the number of neighbors that a vertex has coincides with its degree. A **dominating set** of a graph is a vertex subset whose closed neighborhood includes all vertices of the graph. A vertex *v* **dominates** another vertex *u* if there is an edge from *v* to *u*. A vertex subset *V* **dominates** another vertex subset *U* if every vertex in *U* is adjacent to some 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 column *j* gives the number of edges from the *i*-th to the *j*-th vertex. In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n Ã— n matrix where the nondiagonal entry aij is the number of edges joining vertex and vertex , and the diagonal entry aii is either twice the number of loops at vertex or just...
In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...
**Spectral graph theory** studies relationships between the properties of the graph and its adjacency matrix. In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. ...
The **maximum degree** Δ(*G*) of a graph *G* is the largest degree over all vertices; the **minimum 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*. A 0-regular graph is an independent set. A 1-regular graph is a matching. A 2-regular graph is a vertex disjoint union of cycles. A 3-regular graph is said to be **cubic**, or *trivalent*. In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ...
A *k*-factor is a *k*-regular spanning subgraph. An 1-factor is a *perfect matching*. A partition of edges of a graph into *k*-factors is called a *k*-factorization. A *k*-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 two degrees. A **strongly regular graph** is a regular graph such that any adjacent vertices have the same number of common neighbors as other adjacent pairs and that any nonadjacent vertices have the same number of common neighbors as other nonadjacent pairs.
### Independence In graph theory, the word *independent* usually carries the connotation of *pairwise disjoint* or *mutually nonadjacent*. In this sense, independence is a form of *immediate nonadjacency*. An **isolated vertex** is a vertex not incident to any edges. An **independent set**, or *stable set* or *staset*, is a set of isolated vertices. Since the graph induced by any independent set is an empty graph, the two terms are usually used interchangeably. 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 the size of a largest independent set of *G*. A graph can be **decomposed** into independent sets in the sense that the entire vertex set of the graph can be partitioned into pairwise disjoint independent subsets. Such independent subsets are called **partite sets**, or simply *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 the same as a bipartite graph. A graph that can be decomposed into *k* partite sets is also said to be *k*-colorable. A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...
A **complete multipartite** graph is a graph in which vertices are adjacent if and only if they belong to different partite sets. A *complete bipartite graph* is also referred to as a **biclique**. In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...
A *k*-partite graph is **semiregular** if each of its partite sets has a uniform degree; **equipartite** if each partite set has the same size; and **balanced ***k*-partite if each partite set differs in size by at most 1 with any other. The **matching number** α′(*G*) of a graph *G* is a the size of a largest **matching**, or pairwise vertex disjoint edges, of *G*. A *spanning matching*, also called a **perfect matching** is a matching that covers all vertices of a graph.
## Connectivity Connectivity extends the concept of adjacency and is essentially a form (and measure) of *concatenated adjacency*. In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ...
If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be **connected**; otherwise, the graph is **disconnected**. A graph is **totally disconnected** if there is no path connecting any pair of vertices. This is just another name to describe an empty graph or independent set. A **cut vertex**, or *articulation point*, is a vertex whose removal disconnects the remaining subgraph. A **cut set**, or *vertex cut* or *separating set*, is a set of vertices whose removal disconnects the remaining subgraph. A *bridge* is an analogous edge (see below). In mathematics and computer science, a cut vertex, or articulation point, is a type of graph vertex, the removal of which cause the graph to become disconnected. ...
If it is always possible to establish a path from any vertex to every other one even after removing any *k* - 1 vertices, then the graph is said to be *k*-connected. Note that a graph is *k*-connected if and only if it contains *k* internally disjoint paths between any two vertices. The example graph above is connected (and therefore 1-connected), but not 2-connected. The **connectivity** κ(*G*) of a graph *G* is the minimum 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. (For example, a tree is made entirely of bridges.) A **disconnecting set** is a set of edges whose removal increases the number of components. An **edge cut** is the set of all edges having one endvertex in some proper vertex subset *S* and another endvertex in *V*(*G*)*S*. Edges of *K*_{3} form a disconnecting set but not an edge cut. Any two edges of *K*_{3} 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 a nonempty graph is necessarily an edge cut. A **bond** is a minimal (but not necessarily minimum), nonempty set of edges whose removal disconnects a graph. A *cut vertex* is an analogous vertex (see above). A graph is *k*-edge-connected if any subgraph formed by removing any *k* - 1 edges is still connected. The **edge connectivity** κ′(*G*) of a graph *G* is the minimum number of edges needed to disconnect *G*. One well-known result is that κ(*G*) ≤ κ′(*G*) ≤ δ(*G*). A **component** is a maximally connected subgraph; a **block** is either a maximally 2-connected subgraph or a bridge with its endvertices; and a **biconnected component** is a maximal set of edges in which any two members lie on a common simple cycle. A **separating vertex** of a graph is a vertex whose removal from the graph increases its number of connected components. A biconnected component can be defined as a subgraph induced by a maximal set of nodes that has no separating vertex.
## Distance 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 *G* is usually dropped when there is no danger of confusion. When *u* and *v* are identical, their distance is 0. When *u* and *v* are unreachable from each other, their distance is defined to be infinity ∞. In the mathematical subfield of graph theory we can define a notion of distance between two vertices in a graph. ...
The infinity symbol âˆž in several typefaces The word infinity comes from the Latin infinitas or unboundedness. ...
The **eccentricity** ε_{G}(*v*) of a vertex *v* in a graph *G* is the maximum distance from *v* to any other vertex. The **diameter** diam(*G*) of a graph *G* is the maximum eccentricity over all vertices in a graph; and the **radius** rad(*G*), the minimum. When there are two components in *G*, diam(*G*) and rad(*G*) defined to be infinity ∞. Trivially, diam(*G*) ≤ 2 rad(*G*). Vertices with maximum eccentricity are called **peripheral vertex**. Vertices of minimum eccentricity form the **center**. A tree has at most two 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 by *W*(*G*), is the sum of distances over all pairs of vertices. An undirected graph's **Wiener polynomial** is defined to be Σ *q*^{d(u,v)} over all unordered pairs of vertices *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 edge between all pairs of vertices of *G* with distance at most *k*. A *second power* of a graph is also called a **square**. A *k*-spanner is a spanning subgraph in which every two vertices are at most *k* times as far apart on S than on G. The number *k* is the **dilation**. *k*-spanner is used for studying geometric network optimization.
## Genus A **crossing** is a pair of intersecting edges. A graph is **embeddable** on a surface if its vertices 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. In mathematics, the genus has few different meanings Topology The genus of a connected, oriented surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. ...
A **planar graph** is one which *can be* drawn on the (Euclidean) plane without any crossing; and a **plane graph**, one which *is* drawn in such fashion. In other words, a planar graph is a graph of genus 0. The example graph is planar; the complete graph on *n* vertices, for *n*> 4, is not planar. Also, a tree is necessarily a planar graph. In graph theory, a planar graph is a graph that can be drawn (mathematicians say can be embedded in the plane) so that no edges intersect. ...
When a graph is drawn without any crossing, any cycle that surrounds a region without any edge reaching from the cycle inside to such region forms a **face**. Two faces on a plane graph are **adjacent** if they share a common edge. A **dual**, or *planar dual* when the context needs to be clarified, *G*^{*} of a plane graph *G* is a graph whose vertices represent the faces, including any outerface, of *G* and are adjacent in *G*^{*} if and only if their corresponding faces are adjacent in *G*. The dual of a planar graph is always a planar *pseudograph* (e.g. consider the dual of a triangle). In the familiar case of a 3-connected simple planar graph *G* (isomorphic to a convex polyhedron *P*), the dual *G*^{*} is also a 3-connected simple planar graph (and isomorphic to the dual polyhedron *P*^{*}). A polyhedron is a geometric shape which in mathematics is defined by three related meanings. ...
Furthermore, since we can establish a sense of "inside" and "outside" on a plane, we can identify an "outermost" region that contains the entire graph if the graph does not cover the entire plane. Such outermost region is called an **outer face**. An **outerplanar graph** is one which *can be* drawn in the planar fashion such that its vertices are all adjacent to the outer face; and an **outerplane graph**, one which *is* drawn in such fashion. The minimum number of crossings that must appear when a graph is drawn on a plane is called the **crossing number**. The minimum number of planar graphs needed to cover a graph is the **thickness** of the graph.
## Weighted graphs and networks A **weighted graph** associates a label (**weight**) with every edge in the graph. Weights are usually real numbers. They may be restricted to rational numbers or integers. Certain algorithms require further restrictions on weights; for instance, the Dijkstra algorithm works properly only for positive weights. The **weight of a path** or the **weight of a tree** in a weighted graph is the sum of the weights of the selected edges. Sometimes a non-edge is labeled by a special weight representing infinity. Sometimes the word **cost** is used instead of weight. When stated without any qualification, a graph is always assumed to be unweighted. In some writings of graph theory the term **network** is a synonym for a **weighted graph**. A network may be directed or undirected, it may contain special vertices (nodes), such as **source** or **sink**. The classical network problems include: In mathematics, the set of real numbers, denoted R, is the set of all rational numbers and irrational numbers. ...
Dijkstras algorithm, named after its inventor, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. ...
A labeled graph with 6 vertices and 7 edges. ...
The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks. ...
## Direction An **arc**, or *directed edge*, is an ordered pair of endvertices. In such ordered pair, the first vertex is called a **head**, or *initial vertex*; and the second one, a **tail**, or *terminal vertex*. It can be thought of as an edge associated with a direction, namely designating a head and a tail to the endvertices. An **undirected edge** disregards any sense of direction and treats both endvertices interchangeably. A **loop** in a digraph, however, keeps a sense of direction and treats both head and tail identically. A set of arcs are **multiple**, or *parallel*, if they share the same head and the same tail. A pair of arcs are **anti-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 it contains at least one arc. An **oriented graph** contains only arcs. When stated without any qualification, a graph is almost always assumed to be undirected. Also, a digraph is usually assumed to contain no undirected edges. This article just presents the basic definitions. ...
A digraph is called **simple** if it has no loops and at most one arc between any pair of vertices. When stated without any qualification, a digraph is usually assumed to be simple. In a digraph Γ, we distinguish the **out degree** *d*_{Γ}^{+}(*v*), the number of edges leaving a vertex *v*, and the **in degree** *d*_{Γ}^{-}(*v*), the number of edges entering a vertex *v*. If the graph is oriented, the degree *d*_{Γ}(*v*) of a vertex *v* is equal to the sum of its out- and in- degrees. When the context is 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 *successor set*, *N*^{+}_{Γ}(*v*) of a vertex *v* is the set of tails of arcs going from *v*. Likewise, an **in-neighborhood**, or *predecessor set*, *N*^{-}_{Γ}(*v*) of a vertex *v* is the set of heads of arcs going into *v*. 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*. A vertex subset *S* is **out-dominating** if every vertex not in *S* is dominated by some vertex in *S*; 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 induced sub-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. When stated without any qualification, it is usually assumed that all undirected edges are replaced by a directed one in an orientation. 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, it is an oriented complete graph. One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ...
A **directed path**, or just a *path* when the context is clear, is an oriented simple path such that all arcs go the same direction, meaning all internal vertices have in- and out-degrees 1. A vertex *v* is **reachable** from another vertex *u* if there is a directed path that starts from *u* and ends at *v*. Note that in general the condition that *u* is reachable from *v* does not imply that *v* is also reachable from *u*. If *v* is reachable from *u*, then *u* is a **predecessor** of *v* and *v* is a **successor** of *u*. If there is an arc from *u* to *v*, then *u* is a **direct predecessor** of *v*, and *v* is a **direct successor** of *u*. A digraph is **strongly connected** if every vertex is reachable from every other following the directions of the arcs. On the contrary, a digraph is **weakly connected** if its underlying undirected graph is connected. A weakly connected graph can be thought of as a digraph in which every vertex is "reachable" from every other but not necessarily following the directions of the arcs. A **strong orientation** is an orientation that produces a strongly connected digraph. A **directed cycle**, or just a *cycle* when the context is clear, is an oriented simple cycle such that all arcs go the same direction, meaning all vertices have in- and out-degrees 1. A digraph is **acyclic** if it does not contain any directed cycle. A finite, acyclic digraph with no isolated vertices necessarily contain at least one source and at least one sink. See also directed acyclic graph (dag for short) for more. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...
An **arborescence**, or *out-tree* or *branching*, is an oriented tree in which all vertices are reachable from a single vertex. Likewise, an *in-tree* is an oriented tree in which a single vertex is reachable from every other one.
## Various A **graph invariant** is a property of a graph *G*, usually a number or a polynomial, that depends only on the isomorphism class of *G*. Examples are graph genus and graph order. One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ...
## To be merged Note that prior to the introduction of large computer networks, graph theory was largely a field without widespread interest or application. Since network analysis has become a vital commercial interest, non-academics have crowded the field and popularized certain terms. **graph, network** - An abstraction of relationships among objects. Graphs consist exclusively of nodes and edges. All characteristics of a system are either eliminated or subsumed into these elements.
**diagram** - A visible rendering of the abstract concept of a graph.
**point, node, vertex** - Objects ("things") represented in a graph. These are almost always rendered as round dots.
**edge, link, arc** - Relationships represented in a graph. These are always rendered as straight or curved lines. The term "arc" may be misleading.
**unidentified** - Nodes or edges which are not considered as individuals. Only the way in which they connect to the rest of the graph characterize unidentified nodes and edges.
**color, colored, identified** - Nodes or edges which are considered as individuals. Although they may actually be rendered in diagrams in different colors, working mathematicians generally pencil in numbers or letters.
**undirected** - A graph in which each edge symbolizes an unordered, transitive relationship between two nodes. Such edges are rendered as plain lines or arcs.
**directed, digraph** - A graph in which each edge symbolizes an ordered, non-transitive relationship between two nodes. Such edges are rendered with an arrowhead at one end of a line or arc.
**unweighted** - A graph in which all the relationships symbolized by edges are considered equivalent. Such edges are rendered as plain lines or arcs.
**weighted (edge)** - Weighted edges symbolize relationships between nodes which are considered to have some value, for instance, distance or lag time. Such edges are usually annotated by a number or letter placed beside the edge.
**weighted (vertex)** - Weighted nodes have some value different from their identification.
**adjacent** - Two edges are adjacent if they have a node in common; two nodes are adjacent if they have an edge in common.
**degree** - The number of edges which connect a node.
**regular** - A graph in which each node has the same degree.
**complete** - A graph in which every node is linked to every other node. For a complete digraph, this means one link in either direction.
**route** - A sequence of edges and nodes from one node to another. Any given edge or node might be used more than once.
**path** - A route that does not pass any edge more than once. If the path does not pass any node more than once, it is a
**simple path**. **connected** - If some route exists from every node to every other, the graph is connected. Note that some graphs are
*not* connected. A diagram of an unconnected graph may look like two or more unrelated diagrams, but all the nodes and edges shown are considered as one graph. **loop, cycle** - A path which ends at the node where it began.
**tree** - A connected graph with no loops.
**simplicial vertex** - A vertex v is simplicial if and only if there exists a neighboring vertex u, where u ∪ the neighborhood of u is equivalent to v ∪ the neighborhood of v. Any set of connected simplicial vertices forms a clique.
**Eulerian path** - A path which passes through every edge (once and only once). If the starting and ending nodes are the same, it is an
**Euler cycle** or an **Euler circuit**. If the starting and ending nodes are different, it is an **Euler trail**. **Hamiltonian path** - A path which passes through every node once and only once. If the starting and ending nodes are adjacent, it is a
**Hamiltonian cycle**. The KÃ¶nigsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ...
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ...
## See also A labeled graph with 6 vertices (nodes) and 7 edges. ...
A labeled graph with 6 vertices and 7 edges. ...
This is a list of graph theory topics, by Wikipedia page. ...
## 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.*] - Diestel, Reinhard (2005), "Graph Theory, Third Edition". Springer. ISBN 3-540-26182-6 ["Standard textbook, all basic material and some deeper results, exercises of various difficulty and notes at the end of each chapter; known for being quasi error-free."]
- West, Douglas B. (2001).
*Introduction to Graph Theory* (2ed). Upper Saddle River: Prentice Hall. ISBN 0-13-014400-2. [*Tons of illustrations, 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
- Zaslavsky, Thomas. Glossary of signed and gain graphs and allied areas.
*Electronic Journal of Combinatorics*, Dynamic Surveys in Combinatorics, # DS 8. http://www.combinatorics.org/Surveys/ |