# Adjacency list and the adjacency matrix for the directed cycle with 4 vertices and directed wheel with 5 vertices in total

I have encountered a problem while doing exercises in my text book.

The question is to write down the Adjacency list and the adjacency matrix for the directed cycle with 4 vertices and directed wheel with 5 vertices in total

If you could give me some help, it would be greatly appreciated :)

-
This should be easy, if you know the definitions of those types of graph and of the adjacency matrix. Where do you have problems / what concept do you not understand? – Gregor Bruns Aug 12 '12 at 22:28

This is the directed cycle with $4$ vertices:

This is the directed wheel with $5$ vertices in total:

[I'm assuming the definition here. There might be other definitions, but the process is still the same.]

To write down an adjacency list or adjacency matrix, we need to give the vertices labels. The labels are arbitrary, but it's usually easier to choose labels such as $1,2,\ldots,n$. So let's label the vertices as follows:

and

An adjacency list is simply a list of the edges in the graph. We can just read these from the above drawings:

• The adjacency list for directed cycle with $4$ vertices has adjacency list is $(1,2),(2,3),(3,4),(4,1)$.
• The adjacency list for directed wheel with $5$ vertices has adjacency list is $(1,2),(2,3),(3,4),(4,1),(5,1),(5,2),(5,3),(5,4)$.

Note: these are directed edges, so e.g. $(5,1)$ is different to $(1,5)$.

The adjacency matrix of a directed graph $G$ is a $(0,1)$-matrix with a $1$ in cell $(i,j)$ whenever $(i,j)$ is an edge in $G$ (and $0$ otherwise).

• The adjacency matrix for directed cycle with $4$ vertices is

$$\begin{array}{|cccc|} \hline 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \hline \end{array}.$$

• The adjacency matrix for directed wheel with $5$ vertices is

$$\begin{array}{|ccccc|} \hline 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ \hline \end{array}.$$

One caveat: the adjacency list and adjacency matrix will change depending on which way you label the vertices.

-