Some special types of simple graphs

 1) Complete graphs: In the simple graph that has an edge between any pair of distinct vertices. If it has n vertices, then it is denoted by K_n.

Ex:

\begin{array}{l} Let\;G = {k_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = n\\ - \;\left| E \right| = \left( {\begin{array}{*{20}{c}} n\\ 2 \end{array}} \right)\\ \to 2e = \mathop \sum \limits_{v \in V} \deg \left( v \right) = n\left( {n - 1} \right)\\ \to e = \frac{{n\left( {n - 1} \right)}}{2} \end{array}

- Degree sequence n-1, n-1, n-1, - - - , n-1 . 

- K_n is (n-1) -- regular. 

- K_n is not bipartite for all n > 2 . 

2) Null graphs: Graphs with no edges, denoted by N_nwhen it has n vertices.

Ex: 

\begin{array}{l} Let\;G = {N_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = n\\ - \;\left| E \right| = 0 \end{array}

- Degree sequence 0, 0, 0, - - - , 0 . 

- N_n is 0 -- regular. 

- N_n is bipartite. 

3) Path: The path P_n ( n > 1 ) has n vertices, and n-1 edges. The edges are {v₁, v₂}, {v₂, v₃}, - - - , {v_n-1, v_n}.

Ex: 

\begin{array}{l} Let\;G = {P_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = n\\ - \;\left| E \right| = n - 1 \end{array}

- Degree sequence 2, 2, 2, - - - , 2, 1, 1 . 

- P_n is not regular for n > 2. 

- P_n is bipartite. 

4) The cycle C_n , n > 2 , consist of n vertices, and the edges are {v₁, v₂}, {v₂, v₃}, - - - , {v_n-1, v_n} & {v_n,v₁}.

Ex: 

\begin{array}{l} Let\;G = {C_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = n\\ - \;\left| E \right| = n \end{array}

- Degree sequence 2, 2, 2, - - - , 2 . 

- C_n is 2 -- regular. 

- C_n is bipartite iff n is even. 

5) wheels: The wheel W_n (n > 2) is obtained when an additional vertex is added to the cycle C_n and this new vertex is connected to each of the vertices of C_n .

Ex: 

\begin{array}{l} Let\;G = {W_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = n + 1\\ - \;\left| E \right| = 2n \end{array}

- Degree sequence n, 3, 3, - - - , 3 . 

- W_n is not regular unless n = 3. 

- W_n is not bipartite. 

6) n - Cubes ( n - dimensional hypercube ) denoted by Q_n : The vertex set of Q_n is the set of all bit strings of length n. Two vertices are adjacent iff the bit strings that they represent differ in exactly one bit position.

Ex:

\begin{array}{l} Let\;G = {Q_n} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = {2^n}\\ - \;To\;find\;the\;number\;of\;edges\;\\ 2e = \mathop \sum \limits_{v \in V} \deg \left( v \right) = \mathop \sum \limits_{v \in V} {\rm{n}} = n\;{2^n}\\ \to e = n\;{2^{n - 1}} \end{array}

- Degree sequence n-1, n, n, - - - , n . 

- Q_n is n -- regular. 

- Q_n is  bipartite . 

7) Complete Bipartite Graphs: The complete bipartite graph K_m,n is the graph that has its vertex set partitional into two subsets of m, n vertices respectively. there is an edge between two vertices iff  one vertex is in the first subset and the other vertex is in the second subset. 

Ex: 

\[\begin{array}{l} Let\;G = {K_{m,n}} = \left( {V,E} \right).\;Then\\ - \;\left| V \right| = m + n\\ - \;\left| E \right| = m*n \end{array}\]

- Degree sequence of K_m,n  (m >= n) 

 m, m, - - - , m    ,     n, n, - - - , n . 

- K_m,n  is regular iff m = n. 

- K_m,n  is  bipartite .