In this section we give some very preliminary definitions about graph theory.
Definition 1.4. We define a graph Γ as a couple Γ = (VΓ, EΓ) where VΓ is a not empty finite set of elements called vertices and EΓ is a subset of subsets of VΓ of size 2. If e = {x, y} for some distinct x and y in VΓ, we also say that such elements, x and y, are joined or adjacent. The elements of EΓ are called edges.
Definition 1.5. We define a directed graph ~Γ, or digraph, as a couple ~Γ = (V~Γ, A~Γ) where V~Γ is a not empty finite set of elements called vertices and A~Γ, whose elements are called arcs, is a subset of (V~Γ× V~Γ) \ ∆ where ∆ = {(x, x) | x ∈ V~Γ}. Therefore each a ∈ A~Γ is of joined if there is an edge with an end vertex in X and the other in Y . Given two distinct subsets X and Y of V~Γ, for ~Γ a digraph, we say that X and Y are joined if there is an arc with an end vertex in X and the other in Y . For graphs or digraphs, if Γ or ~Γ is clear from the context, then we write (V, E) instead of (VΓ, EΓ) and (V, A) instead of (V~Γ, A~Γ).
The cardinality of the vertex set of both graphs and digraphs is called the order of the graph/digraph.
Usually, in graph theory, each vertex of a graph Γ is represented as a point; an edge {x, y} ∈ E is a line joining vertex points x and y.
For a digraph ~Γ the representation is quite similar, with the only exception that an arc (x, y) ∈ A~Γ it is no more a line between the two end vertices, but an arrow that is directed from x to y.
In Figure 1.1 an example of a complete graph and a complete digraph.
Definition 1.6. Let Γ be a graph. The digraph obtained by replacing each edge of Γ by just one of the two possible arcs with the same ends is called an orientation of Γ.
In Figure 1.2 there are some possible orientation of K4.
Definition 1.7. A path is a graph whose vertices can be arranged in an ordered sequence in such a way that two vertices are adjacent if and only if they are consecutive in the sequence.
A directed path is an orientation of a path in which each vertex dominates its successor in the sequence.
For a path W, |EW| is the length of W, denoted as `(W). A k-path is a path with length k. Likewise `( ~W) := |AW~| is the length of a directed path ~W and a directed k-path is a directed path of length k.
Figure 1.1: K5 and ~K4
Figure 1.2: Some possible orientation of K4.
a b c d
By definition, the vertices of a path W can be arranged in an ordered sequence such that two vertices are adjacent if and only if they are consecutive in the sequence. There exist two of such arrangements, both of them determine the path W. If, for k ∈ N, VW = {x1, . . . , xk} and EW = {{xi, xi+1} | i ∈ [k − 1]}, then W is uniquely determined by both the ordered sequences x1, x2, . . . , xk and xk, xk−1, . . . , x1. So we represent the path W as one of those arrangements. Hence we write W = x1, x2. . . , xk. In such a representation x1 and xk are called the end vertices of W.
It is similar for directed paths, but there are some differences. For a directed path ~W there exists only one ordered sequence that determine the path.
W = x~ 1, . . . , xk is a directed path with VW~ = {x1, . . . , xk} and AW~ = {(xi, xi+1) | i ∈ [k − 1]}. x1 and xk are the end vertices of ~W. We also say that ~W starts in x1 and ends in xk.
In Figures 1.3 and 1.4 there are three examples of path and directed path. Note that W1 and W2 are two distinct orientation of W in Figure 1.3.
Definition 1.8. A cycle on three or more vertices is a graph whose vertices can be arranged in a cyclic sequence so that two vertices are adjacent if and only if they are consecutive in the sequence.
A directed cycle is an orientation of a cycle in which each vertex dominates its successor in the cyclic sequence.
Let C be a cycle and ~C a directed cycle. |EC| is the length of the cycle and |AC~| is the length of the directed cycle, denoted, respectively, `(C) and `( ~C). A k-cycle and a directed k-cycle are, respectively, a cycle of length k and a directed cycle of length k.
As in the case of paths, we represent a cycle with an ordered list of vertices. Note that, for a cycle C, there exist more then two possible arrangements that determine the same cycle, indeed C does not have ending points. In fact, a cycle C with VC = {x1, . . . , xk}
a b Also for a directed cycle ~C there exist more than two possible ordered sequences of vertices that determine the cycle. Consider ~C with VC~ = {x1, . . . , xk} and AC~ = {(xi, xi+1) | i ∈ [k − 1]} ∪ {(xk, x1)}. The sequences
xi, xi+1, . . . , xk, x1, x2, . . . , xi−1, xi
for all i ∈ [k] determine uniquely the directed cycle ~C.
Hence we write ~C = x1, x2. . . , xk, x1.
There are three examples of cycles and directed cycles in Figures 1.5 and 1.6. Note that ~C1 and ~C2 are distinct orientations of C.
Definition 1.9. Let Γ1 and Γ2 be two graphs. A map ψ : VΓ1 → VΓ2 is a graph homo-morphism if it maps adjacent vertices to adjacent vertices. Formally {x, y} ∈ EΓ1 implies {ψ(x), ψ(y)} ∈ EΓ2 for all x, y ∈ VΓ1. If ψ is a graph homomorphism between Γ1 and Γ2, then we use the notation ψ : Γ1 → Γ2
Definition 1.10. Two graphs Γ1 and Γ2 are said to be isomorphic, in symbols Γ1 ∼= Γ2, if there exists an homomorphism ψ that is a bijection between VΓ1 and VΓ2 with the property that {x, y} ∈ EΓ1 if and only if {ψ(x), ψ(y)} ∈ EΓ2. Such a ψ is called graph isomorphism. If Γ1 = Γ2, then ψ is also called graph automorphism.
Analogous definition can be given for digraphs.
Figure 1.7: A graph with |SΓ| = 1
Definition 1.13. Given a vertex x of a graph Γ, the closed neighbourhood of x in Γ is defined as the set NΓ[x] = {y ∈ VΓ| y = x or {y, x} ∈ EΓ}.
The open neighbourhood of x in Γ is defined as the set NΓ(x) = NΓ[x] \ {x}.
NΓ[x] is never an empty set as it always contains the vertex x, indeed 1 ≤ |NΓ[x]| ≤ |VΓ|.
If |NΓ[x]| = |VΓ|, and hence NΓ[x] = VΓ, then x is called a star vertex. We denote the set of all star vertices of Γ by SΓ. In Figure 1.7 the vertex in the centre is the only star vertex. Note that Γ is a complete graph if and only if SΓ= VΓ. Look at Figure 1.1 to see the case of K5.
Remark 1.14. Let Γ1 and Γ2 be two graphs. If Γ1 ∼= Γ2, Then |SΓ1| = |SΓ2|.
Proof. Let ψ be an isomorphism between the two graphs Γ1 and Γ2. Now let x, y ∈ VΓ1, with y 6= x. Since ψ is a graph isomorphism, then we have that {x, y} ∈ EΓ1 if and only if {ψ(x), ψ(y)} ∈ EΓ2. Hence x ∈ SΓ1 if and only if ψ(x) ∈ SΓ2. Thus |SΓ1| = |SΓ2|, since ψ is a bijection between VΓ1 and VΓ2.
In general |NΓ[x]| − 1 is called the degree of x, also denoted by degΓ(x). We use deg(x) when Γ is clear from the context.