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