# Dictionary Definition

thickness

### Noun

1 the dimension through an object as opposed to
its length or width [ant: thinness]

2 used of a line or mark [syn: heaviness]

3 resistance to flow [ant: thinness]

# User Contributed Dictionary

## English

- The property of being thick (in dimension).
- When it comes to penis size, many women say they prefer thickness over length.

- A measure of how thick (in dimension) something is.
- The thickness of the Earth's crust is varies from two to 70 kilometres.

- A layer.
- We upholstered the seat with three thicknesses of cloth to make it more comfortable to sit on.

- The quality of being thick (in consistency).
- Whip the cream until it reaches a good thickness.

- In the context of "uncountable|informal": The property of being thick (slow to understand).

#### Synonyms

#### Antonyms

- (in consistency): fluidity, liquidity, runniness, thinness, wateriness
- (property of being stupid): mental acuity, mental agility, quick-wittedness, sharpness

#### Translations

measure

layer See layer

in consistency

- German: Dicke

informal: property of being stupid

- Spanish: torpeza

# Extensive Definition

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.

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

Alternative models of graph exist; e.g., a graph
may be thought of as a Boolean binary
function over the set of vertices or as a square (0,1)-matrix.

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

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.

An anti-edge is an edge that "is not there". More
formally, for two vertices u and v, \ is an anti-edge in a graph G
whenever \ is not an edge in G. This means that there is either no
edge between the two vertices or (for directed graphs) at most one
of (u, v) and (v, u) from v is an arc in G.

An anti-triangle is a set of three vertices none
of which are connected.

The complement \bar 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 \bar if and only if xy is not an edge in G.

An edgeless graph or empty graph is a graph with
zero or more vertices, but no edges.

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

### 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 all the edges that appear in G over the
same vertex set. If the vertex set of H is the 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 (a vertex is counted each time it is 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 understood
to be simple, meaning that no vertices (and thus no edges) are
repeated. (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 Pn and Cn, respectively. (Some
authors use the length instead of the number of vertices,
however.)

C1 is a loop, C2 is a pair of digons (multiple
edges), and C3 is called a triangle.

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 it contains no odd cycles. (See complete
bipartite graph.)

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

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

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.

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 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 theta0 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; in this case, the tree is
called rooted. Rooted trees are often treated as directed
acyclic graphs with the edges pointing away from the
root.

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

A subtree of the tree T is a connected 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 special kind of tree called a star is K1,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. A 1-ary tree is just a path. A
2-ary tree is also called a binary tree.

### Cliques

The complete
graph Kn 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 Kn.
It has n(n-1)/2 edges (corresponding to all possible choices of
pairs 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. A
maximal
clique is a clique that is not a subset of any other
clique.

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 GT is the graph
G with all the edge directions reversed.

### 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 terminate at other vertices in the knot. 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.

### 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)).### 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.## 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, dG(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.

The total degree of a graph is equal to two times
the number of edges, loops included. This means that for a graph
with 3 vertices with each vertex having a degree of two (e.g. a
triangle) the total degree would be six (e.g. 3 x 2 = 6). The
general formula for this is total degree = 2n where n = number of
edges.

A degree sequence is a list of degrees of a graph
in non-increasing order (e.g. d1 ≥ d2 ≥ … ≥ dn). A sequence of
non-increasing integers is realizable if it is a degree sequence of
some graph.

Two vertices u and v are called adjacent if an
edge exists between them. We denote this by u ~ v or 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 NG(v). When v is also included,
it is called a closed neighborhood and denoted by NG[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.

Spectral
graph theory studies relationships between the properties of
the graph and 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.

A k-factor is a k-regular spanning subgraph. A
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, i.e., no pair of vertices is adjacent. 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 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; if its
partite sets contain n and m vertices, respectively, then the graph
is denoted Kn,m.

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 \alpha'(G) of a graph G is
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''.

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

If it is always possible to establish a path from
any vertex to every other 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 that need to be
removed to disconnect G. By convention, Kn 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, all the edges in a
tree are 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 which have one vertex in some proper vertex subset S
and the other vertex in V(G)\S. Edges of K3 form a disconnecting
set but not an edge cut. Any two edges of K3 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 \kappa'(G) of a graph G is the minimum number of edges
needed to disconnect G. One well-known result is that \kappa(G) \le
\kappa'(G) \le \delta(G).

A component is a maximally connected subgraph. A
block is either a maximally 2-connected subgraph, a bridge
(together with its vertices), or an isolated vertex. A biconnected
component is a 2-connected component.

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
dG(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 ∞.

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 vertices. 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 WG(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 Σ qd(u,v) over all unordered pairs of
vertices u and v. Wiener index and Wiener polynomial are of
particular interest to mathematical chemists.

The k-th power Gk 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.

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.

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

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 writing on
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:

- minimum cost spanning tree,
- shortest paths,
- maximal flow (and the max-flow min-cut theorem)

## Direction

A directed arc, or directed edge, is an ordered
pair of endvertices that can represented graphically as an arrow
drawn between the endvertices. In such an ordered pair the first
vertex is called the initial vertex or tail; the second one is
called the terminal vertex or head (because it appears at the arrow
head). 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, or oriented graph, is analogous to an undirected graph
except that it contains only arcs. A mixed graph may contain both
directed and undirected edges; it generalizes both directed and
undirected graphs. When stated without any qualification, a graph
is almost always assumed to be undirected.

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.

The zweieck of an undirected edge e=(u,v) is the
pair of diedges (u,v) and (v,u) which form the simple
dicircuit.

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.

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
contains at least one source and at least one sink. See also
directed
acyclic graph (dag for short) for more.

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.

## Colouring

Vertices in graphs can be given colours to identify or label them. Although they may actually be rendered in diagrams in different colours, working mathematicians generally pencil in numbers or letters (usually numbers) to represent the colours.Given a graph G (V,E) a k-colouring of G is a map
ϕ : V → with the property that (u, v) ∈ E ⇒ ϕ(u) ≠ ϕ(v) - in other
words, every vertex is assigned a colour with the condition that
adjacent vertices cannot be assigned the same colour.

The chromatic number χ(G) is the smallest k for
which G has a k-colouring.

## 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 the order, genus, chromatic
number, and chromatic
polynomial of a graph.

## 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. ;diagram, drawing : A visible rendering of the abstract concept of a graph. ;edge, link, arc : Relationships represented in a graph. These are always rendered as straight or curved lines. The term "arc" may be misleading. ;undirected : A graph in which each edge symbolizes an unordered, transitive relationship between two nodes. Such edges are rendered as plain lines or arcs. ;unweighted : A graph in which all the relationships symbolized by edges are considered equivalent. Such edges are rendered as plain lines or arcs. ;weighted (vertex) : Weighted nodes have some value different from their identification.;regular : A graph in which each node has the same degree. ;route : A sequence of edges and nodes from one node to another. Any given edge or node might be used more than once. ;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. ;tree : A connected graph with no loops. ;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.## See also

## References

- [1] Graph Triangulation, Jayson Rome, October 14, 2002 http://prl.cs.gc.cuny.edu/web/LabWebsite/Rome/jrome/Slides_Tutorials/GraphTriangulation.pdf
- 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.]
- [Standard textbook, most basic material and some deeper results, exercises of various difficulty and notes at the end of each chapter; known for being quasi error-free. Free electronic version is available.]
- 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.]
- 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/

thickness in German: Glossar
Graphentheorie

thickness in Spanish: Glosario en teoría de
grafos

thickness in French: Lexique de la théorie des
graphes

thickness in Korean: 그래프 이론 용어사전

thickness in Italian: Glossario di teoria dei
grafi

thickness in Japanese: グラフ理論

thickness in Hungarian: Gráfelméleti
fogalomtár

thickness in Portuguese: Glossário de teoria dos
grafos

thickness in Russian: Словарь терминов теории
графов

thickness in Thai: อภิธานศัพท์ทฤษฎีกราฟ

thickness in Vietnamese: Thuật ngữ lý thuyết đồ
thị

# Synonyms, Antonyms and Related Words

adhesiveness, band, bed, bedding, belt, bodily size, body, bulk, cacophony, clabbering, clamminess, closeness, clotting, coagulation, coarseness, colloidality, compactness, congestedness, congestion, consistence, consistency, corpulence, couche, course, cracked voice, crowdedness, curdling, deck, denseness, density, depth, discord, distance through,
doughiness, dryness, fatness, firmness, floor, gallery, gelatinity, gelatinousness, gluelikeness, gluiness, glutinosity, glutinousness, grossness, gruffness, gumlikeness, gumminess, gutturalism, gutturality, gutturalness, hardness, harshness, heaviness, hoarseness, huskiness, impenetrability,
impermeability,
imporosity, incompressibility,
incrassation,
inspissation,
jammedness, jellification, jellylikeness, layer, ledge, lentor, level, mass, measures, mucilaginousness,
overlayer, overstory, pastiness, raspiness, raucity, relative density,
ropiness, roughness, rudeness, scrapiness, scratchiness, seam, shelf, slabbiness, sliminess, solidity, solidness, specific gravity,
spissitude, stage, step, stertorousness, stickiness, stodginess, story, stratum, stringiness, substratum, superstratum, syrupiness, tackiness, tenaciousness, tenacity, the third dimension,
thickening, throatiness, tier, topsoil, toughness, treacliness, ugliness, underlayer, understory, understratum, viscidity, viscosity, viscousness, zone