# Graph

We state here basic definitions from graph theory used in the articles. For more details we refer the interested reader to the literature.

## Contents

## Undirected graph

A **graph** or an **undirected graph** is a tuple with

- a nonempty set whose elements are called
*vertices, nodes*or*points* - a (possibly empty) set of unordered pairs of elements of V called
*links*or*edges*

- a nonempty set whose elements are called

(Here we restrict ourselves to the terms vertex and edge to refer to elements of and , respectively.)

For an edge with the vertices
and are called **endpoints** of edge .
Vertices and are **adjacent** if they are connected by an edge . Furthermore we say edge is **incident** to vertices v and w.

Two edges sharing one common endpoint are called **adjacent**, too.

We call an edge a **loop** if its endpoints are identical
(), and edges are called **multi-edges**.
A graph containing no multi-edges or loops is called **simple graph**.

The **degree**, , of a vertex is the total number of its **incident** edges.

The **order** of a graph , is defined as the cardinality of the (vertex) set . The **size** of a graph, denoted by , is the cardinality of the (edge) set .

## Complete graph

A graph is called **complete graph** if
.
See for example the complete graph .

## Bipartite graph

A graph is called bipartite if its vertex set can be partitioned into two disjoint subsets such that every edge of joins with , i.e. , and no edge connects vertices in only or only.

## Directed graph

A **directed graph** or **digraph** is a graph with
(edge) set consisting of ordered pairs of vertices, called **arcs**, **directed edges** or **arrows**.

Let . We call **tail** and **head** of arc .
Further on, is called (direct) predecessor of which is a (direct) successor of . We skip the term *direct* if are connected via a path with length greater than 1.

The **indegree** () of a vertex is defined as the number of arcs of the form (e.g. is the head of the arcs), similarly the **outdegree** () of
a vertex is defined as the number of arcs where is tail (e.g. arcs of the form: ).

A directed graph having no multi-edges or loops is called a **simple directed graph**. A complete graph in which each edge is bidirected is called a **complete directed graph**. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an **oriented graph**. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single edge having a unique direction) is called a **tournament**.

## Walk, path, and cycle

Let be a graph. A **walk** in is a sequence of vertices , , such that , for .
A walk is called **closed** if and . A walk without any repeated vertex is called **path**.
A closed path is called **circuit** or **cycle**. The **length**
of a walk is the number of edges of the walk.

Similiarly, a **directed walk** is a sequence of , , such that , for .
Furthermore, if and , then is closed. A **directed path** is a directed walk without repetitions. A **directed cycle** (or **circuit**) is a closed directed path.

## Tree and forest

A connected simple graph without cycles is called a **tree**. If the graph is simple but disconnected, i.e there are more than one component,
and there exists no cycle then we call the graph a forest.

## Acyclic graph (DAG)

A directed graph is called directed acyclic graph if it contains no directed cycle.

## Connectivity

Two nodes are **connected** if the graph contains at least one path from v to w.

A graph is connected if every pair of its nodes is connected.

A graph is **strongly connected** if each two nodes are adjacent.

## Cut

A Cut is a partition of the vertices of a graph into two sets and . Any edge with and is a cut edge.

We denote the set of cut edges with .

## Eulerian graph

Let be a connected graph. is called Eulerian iff every vertex of has even degree. This is equivalent to saying that the edge set of can be partitioned into cycles

## Weighted graph

Let be a graph (undirected or directed). A **weight function** (or a **cost function**) for
is a mapping .

If and satisfies the triangle inequality then we call a **distance function** for .

Let be a path in . The weight of the path is denoted by .

## Subgraph

A graph is a **subgraph** of , if and . We say is a **vertex-induced** subgraph of , if and .

Similarly we say is an **edge-induced** subgraph of , if and , i.e the vertex set of is restricted to vertices occuring in .

A graph which is constructed from by repeated edge deletion and/or contraction is called a **minor** of . Contraction of an edge means the replacement of and by a single vertex such that all edges other than that were incident to and are now incident to the new vertex.

A subdivision of graph is defined on the graph that arises from by (repeatedly) replacing an edge of by two edges and one new vertex.

*Formally:* Let and , then is a subdivision of .

## Clique, independent set

A **clique** in a graph is a set of vertices such that for every pair of vertices , there exists an edge .
This is equivalent to saying that the subgraph induced by is a complete graph. The size of a clique is the number of vertices it contains.

The "opposite" of a clique is an **independent set**, i.e. a set of vertices such that no two
vertices are adjacent,
in the sense that every clique corresponds to an independent set in the complement graph.

## Planar graph

A graph is planar if it can be drawn in the plane in such
a way that no two edges meet each other except at a vertex to which they are

both incident. Any such drawing is called a **planar drawing** of .

## Dual graph

A (geometric) **dual graph** of an (embedded) connected planar graph is a planar graph with the properties:

has a node for each face of and an edge for each edge joining two neighboring faces (including loops and multi-edges),
(cf. [Harary (1989)]).

## Complement graph

The **complement** or **inverse** of a graph is a graph on the same vertices such that two vertices are adjacent in if and only if they are not adjacent in .

More formally, given a graph , its **complement graph** is defined by:

and

- for a clique of vertices, .

For simple graphs (without multiple edges) we note that the complement of the complement graph yields the original graph again.

## Grid graph

We call a graph planar (rectangular) *grid graph*, if can be embedded in the plane such that each vertex is identified with an unique coordinate and
any two vertices are adjacent if and only if the Manhattan distance between those two vertices equals 1,
i.e. , with , , see Fig. 1.

In other words, any finite subgraph of the 2 dimensional rectangular grid is called a grid graph. Grid graphs form a class of planar graphs that arise in many applications, such as ground state calculations of Ising spin glasses or design of VLSI circuits. Rectangular grid graphs are those grid graphs whose outer boundary is a rectangle and whose bounded faces all are unit squares.

We call a rectangular grid graph *ring graph* if the edge set also includes periodic boundary edges on one side, see Fig. 2.

If periodic boundary edges are present on both sides we call the rectangular grid graph a *toroidal grid graph* or *torus*, cf. Fig. 3.

Note that toroidal grid graphs cannot be embedded in the plane without edge crossings, but can be on the torus.