1.1.4 Special graphs with special notations
A
graph G is regular of degree r if
for each vertex v of G.
Such graphs are called r-regular.

A graph is complete if every two of its vertices are adjacent.
A
complement of a graph G is that graph such that
, and for any
iff
.
A
graph G is k -partite, k
1, if it is possible to partition
into k subsets
(called partite sets) such that
every element of
joins a vertex of
to a vertex of
,
. For k = 2, the graph is
called as bipartite graph.
A
complete k -partite graph with partite sets and
is k -partite graph having
the added property that
if
and
then
. It is
denoted by
. The complete bipartite graph with
and
is denoted by
or
(
is a star).