1.  Consider the following 4-vertex graph G:

2

3

(a)  (4 marks) Write down the adjacency matrix A and the Laplacian matrix L of G.  (Just type

each matrix row-by-row as you would do intuitively.)

(b)  (3 marks) Calculate the (0, 0)-entry of A4 , explaining your calculation or argument.

(c)  (3 marks) Find an eigenvector for G with eigenvalue -1, explaining your argument.

2.   (a)  (3 marks) Calculate the Wiener index for each of the paths P3  and P4 , shown below.

(b)  (3 marks) Suppose that the graph G has spectrum

λ 1 , λ2 , . . . , λn ,

and that graph H has spectrum

µ 1 , µ2 , . . . , µm .

Determine the spectrum of the disjoint union G u H , explaining your argument.

(c)  (4 marks) The three graphs A, B and C drawn below are all 3-regular graphs on 10 vertices.  The algebraic connectivities µ2 (A), µ2 (B) and µ2 (C) of these three graphs are 2.000, 1.121 and 0.438 (to 3 decimal places), but not necessarily in that order.

Use your knowledge of the properties of the algebraic connectivity in order to determine which of the three values is the algebraic connectivity of each of the three graphs.   Explain your reasoning.

A

B

C

3. The icosahedron I is a regular graph with characteristic polynomial

ϕI (x) = (x - 5) . (x + 1)5  . (x2 - 5)3 .

Answer the following questions, making sure you explain your working.  (You may use results given in lectures without proving them provided you state them clearly.)

(a)  (3 marks) How many vertices and edges does I have?

(b)  (3 marks) How many triangles does I have?

(c)  (4 marks) How many spanning trees does I have? (Give a numerical answer.)

4.   (a)  (6 marks) Rounded to three decimal places, the Perron vector of the pictured graph is

(0.244, 0.211, 0.231, 0.292, 0.300, 0.266, 0.282, 0.462, 0.324, 0.374, 0.244).

5 

i. Identify the two most important vertices according to degree centrality.

ii. Identify the two most important vertices according to eigenvector centrality.

iii. Find the spectral radius of this graph.

(b)  (*)  (4 marks) The Paley graph  P (9) is a 9-vertex regular graph that is isomorphic to its

complement,  and has just three distinct eigenvalues.   Find the spectrum of P (9), carefully explaining your argument.

5.  Consider the graph shown below

(a)  (3 marks) What is the empirical degree distribution of the graph?

(b)  (4 marks) What is the average nearest neighbour degree of each vertex?

(c)  (3 marks) What is the transitivity of the graph?

6.  Consider the graph shown below

(a)  (4 marks) What is the coreness of each vertex in the graph?

(b)  (3 marks) What are the vertices involved in the 3-core and 4-core of the graph?

 (c)  (3 marks) Determine the network density of the graph, and then provide an estimate of the connection probability p if the graph was a realization of an Erd˝os-R´enyi random graph model?

7.  Consider the graph shown below

(a)  (4 marks) What is the modularity of the following vertex-partition: {{0}, {1, 2, 3, 4}, {5, 6, 7}}?

(b)  (3 marks) What is the closeness centrality of vertex 4?

(c)  (3 marks) Which of the two communities in Part (a) should be merged, if applicable, to produce the maximum increase in modularity, and what is the new modularity score?

8.  Consider the graph shown below

(a)  (3 marks) For each vertex, what is the probability of a newcomer vertex to preferentially attach

an edge to it?

(b)  (4 marks) Suppose a newcomer vertex has attached an edge to vertex 0 and has a second edge

to attach. What is the probability that a 4-cycle is formed once the second edge is attached to existing vertices?

(c)  (3 marks) Consider the graph as shown above.  If a newcomer vertex has two edges to attach to existing vertices, which two vertices should it attach to to maximize the average clustering coefficient of the graph? Justify your answer.