ABSTRACT
We begin by discussing some theory of graphs and digraphs. Before we do, we
shall remind ourselves of some standard notation. The complete graph Kn
on V is any simple graph of order n with all ( n 2
) edges. The empty graph En
is any graph of order n with no edges. The path Pn of order n has vertex set
[n] with edges {i, i+1} for i = 0, . . . , n−2. The cycle Cn of order n has vertex set [n] with edges {i, i+1} for i = 1, . . . , n, with addition modulo n (a cycle of order 1 is a loop, while a cycle of order 2 consists of two parallel edges). The
complete k-partite graph Kl1,l2,...,lk has vertex set V = V1 ∪ · · · ∪ Vk, where the Vi’s are disjoint and |Vi| = li, and edge set {uv : u ∈ Vi, v ∈ Vj , i 6= j}. In the case k = 2, we say bipartite rather than 2-partite. The stars are
the graphs K1,l. A forest is a graph that contains no cycles, and a tree is a
connected forest.
