1.   (a)  Consider the directed graph shown below, in which the vertices have been numbered according to a certain labelling λ .

i.  [5] Give its adjacency matrix MA   and use it to calculate the number of paths of length four which start at vertex-2 and end at vertex-3.

ii.  [15] Let µ be a labelling of the same graph such that λ(1) = µ(2), λ(2) = µ(3) and λ(3) = µ(1). Give a representation of the graph with labelling µ, and find the adjacency matrix Mμ .  Find the similarity transformation which relates Mμ  and MA  and show how Mμ  is obtained from MA .

(b)  [10] Let M be the adjacency matrix of a loop-free directed graph. If

all the diagonal entries of M2  are zero, what can we deduce about the graph?

2. Let G be the weighted graph shown below.

(a)  [5] Give its transition matrix W and find its stationary states.

(b)  [15] Find the Jordan form of W  and decide if its integer powers

converge as the power increases without bound.

(c)  [10] Use your results to decide whether all states defined on G con- verge to a stationary state as they evolve forwards in time.  If yes, give the state to which any initial state will converge.

3.  Consider the weighted graph shown below.

(a)  [15] Find the probability that a random walk on this graph which

starts at vertex-1 will return to it in exactly n steps (and no earlier).

(b)  [5] By means of the probabilities found above, decide whether every

random walk on this graph which starts at vertex-1 will eventually return to it.

(c)  [10] Calculate the expected time of first return for random walks starting and ending at vertex-1.

4.   (a)  [10] A connected planar graph has vertices of degree either five or six only, and all its faces have degree three. Find the number of vertices of degree five.

(b)  [10] The average face degree of an undirected planar graph is defined

as  Give an expression for the average face degree

of a trivalent connected planar graph (one whose vertices all have degree three) in terms of its number of faces.  Then show that all sufficiently large graphs of this kind have approximately the same average face degree.

(c) For each of the following graphs,  use the Kuratowski theorem to decide whether an equivalent planar representation exists (you don’t need to quote the theorem.)