Null GraphsA null graphs is a graph containing no edges. The null graph with n vertices is denoted by Nn. The following are the examples of null graphs.
Note that Nn is regular of degree 0.
Cycle GraphsA cycle graph is a graph consisting of a single cycle. The cycle graph with n vertices is denoted by Cn. The following are the examples of cyclic graphs.
Note that Cn is regular of degree 2, and has n edges.
Path GraphsA path graph is a graph consisting of a single path. The path graph with n vertices is denoted by Pn. The following are the examples of path graphs.
Note that path graph, Pn, has n-1 edges, and can be obtained from cycle graph, Cn, by removing any edge.
Bipartite GraphsA bipartite graph is a graph whose vertex-set can be split into two sets in such a way that each edge of the graph joins a vertex in first set to a vertex in second set. The examples of bipartite graphs are:
6.25 4.36 9.02 3.68
Complete Bipartite Graph
A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge. The complete bipartite graph with r vertices and 3 vertices is denoted by Kr,s. The following are some examples.
Note that Kr,s has r+s vertices (r vertices of degrees, and s vertices of degree r), and rs edges. Note also that Kr,s = Ks,r. An Important Note: A complete bipartite graph of the form Kr,s is called a star graph.
Cube GraphThe cube graphs is a bipartite graphs and have appropriate in the coding theory. The cube graphs constructed by taking as vertices all binary words of a given length and joining two of these vertices if the corresponding binary words differ in just one place. The binary words of length k is called the k-cube (or k-dimensional cube) graph and is denoted by Qk. The following are some examples.
Notethat Qk has 2k vertices and is regular of degree k. It follows from consequence 3 of the handshaking lemma that Qk has k* 2k-1 edges.
The Peterson GraphThis graph is named after a Danish mathematician, Julius Peterson(1839-1910), who discovered the graph in a paper of 1898.
Tree GraphA tree is a connected graph which has no cycles.
Spanning TreeIf G is a connected graph, the spanning tree in G is a subgraph of G which includes every vertex of G and is also a tree. Consider the following graph
The following are the three of its spanning trees:
Interval GraphsConsider the intervals (0, 3), (2, 7), (-1, 1), (2, 3), (1, 4), (6, 8) which may be illustrated as
We can construct the resulting interval graphs by taking the interval as vertices, join two of these vertices by an edge whenever the corresponding intervals have at least one point in common.
Notethat since the intervals (-1, 1) and (1, 4) are open intervals, they do not have a point in common.
Definition of DiagraphA directed graph or diagraph D consists of a set of elements, called vertices, and a list of ordered pairs of these elements, called arcs. The set of vertices is called arcs. The set of vertices is called the vertex-set of D, denoted by V(D), and the list of arcs is called the arc-list of D, denoted by A(D). If v and w are vertices of D, then an arc of the form vw is said to be directed from v to w, or to join v to w.
The underlying graph of diagraph is the graph obtained by replacing each arc of diagraph by corresponding (undirected) edge. For example, consider the following digraph
The underlying graph of the above digraph is