Graph (discrete mathematics)

1. (Weight 15 %) In graph theory, a rook’s graph is a graph that represents all legal moves of

the rook chess piece on a chessboard. Each vertex of a rook’s graph represents a square on

a chessboard, and each edge represents a legal move from one square to another.

(a) Draw the 3 × 3 rook’s graph associated to the following chessboard.

9 7 3

5 2 8

1 4 6

(b) Show that the 3 × 3 rook’s graph is isomorphic to its complement graph.

(c) Express the 3 × 3 rook’s graph as a product of two known graphs.

2. (Weight 10 %)

a) Determine the value(s) of t satisfying that the number sequence

t− 2, t− 1, t− 1, t, t + 1, t + 1, t2 − 10,

is graphic.

b) Let G be a graph whose degree sequence was obtained in the previous item. What is

the size of the complement of the line graph of G?

3. (Weight 10 %) Let G be the graph whose adjacency matrix is given in the attached file

A2018.txt.

a) Draw the spanning tree T that results when Algorithm Breadth-First Search (BFS) is

applied to G, starting at vertex 1. Use the numerical order as the default priority.

b) Find the diameter of D(T + (T ∪ T)), T�Q4 and T � (K4,7 � Q4), where Q4 is the hypercube of dimension 4.

4. (Weight 5 %) Represent the arithmetic expression (a+b)/((a+ (b×c))−d) by an expression tree. Determine the preorder and postorder traversals of the tree of the arithmetic expression.

5. (Weight 30 %) Let G be a weighted graph whose adjacency matrix is in the attached file

M2018.txt. Consider that the vertex set is V = {A,B,. . . ,J}, where the rows and columns of the matrix correspond to the vertices in alphabetical order.

a) Apply Dijkstra’s algorithm to determine the distance from vertex A to all other vertices

in G. Construct the table of the algorithm and find a shortest path to go from vertex

A to vertex G.

b) Apply Floyd’s algorithm to determine the distance between each pair of nodes.

c) Apply Prim’s algorithm to graph G, starting at vertex A to determine a minimum

spanning tree of G.

6. (Weight 20 %) In chemical graph theory, the Wiener index, denoted by W(G), is a topological

index defined as the sum of the lengths of the shortest paths between all pairs of vertices in

the chemical graph G:

W(G) = ∑

{u,v}⊆V (G)

d(u,v).

Harry Wiener introduced it in 1947 and showed that the Wiener index is closely correlated

with the boiling points of alkane molecules. Later works on quantitative structure-activity

relationships showed that it is also correlated with other quantities.

Find a formula for W(Kn �Pr) in terms of n and r.

7. (Weight 10 %) The Randić Index R(G) of a graph G = (V,E) was defined in 1975 as

R(G) = ∑ {u,v}∈E

1√ δ(u)δ(v)

.

This invariant, sometimes called the connectivity index, has been successfully related with

several physical, chemical, and pharmacological properties of organic molecules. In addition,

this topological index has become one of the most popular molecular descriptors.

Find a formula for R(Kn �Cr) in terms of n and r.