B.Sc (Hons) IV (Fourth) Semester Examination 2012-13

Course Code:BAS604 Paper ID:0832405

Graph Theory

Time: 3 Hours Max. Marks: 70 Max Marks: 75

Note: Attempt six questions in all. Q. No. 1 is compulsory.

1. Answer any five of the following (limit your answer to 50 words). (4x5=20)

a) For which values of n are the following graphs Eulerian?

i) the wheel Wn ii) the complete graph Kn

b) Construct a graph G with the following properties : Edge connectivity of , vertex connectivity of , and degree of every vertex of .

c) Determine the number of crossings and the thickness of the Petersen graph.

d) Characterize a graph for which the circuit space contains the vector .

e) Examine whether a graph with the adjacency matrix:

is connected.

f) Let . Draw the graph G whose vertex set is S and such that for if or .

g) Find all fundamental circuits in the following graph.

Also write its fundamental circuit matrix.

h) If G is a graph without loops , what can you say about the sum of the entries in

i) any row or column of the adjacency matrix of G?

ii) any row of the incidence matrix of G?

iii) any column of the incidence matrix of G?

2. a) Illustrate with atleast two examples how graphs can be used in modeling. (5)

b) Define graph isomorphism. Examine whether the following graphs are isomorphic. (5)

b) Connectivity and separability in a graph.

3. a) Define centre of a tree. Prove that every tree has either one or two centres. (5)

b) Illustrate two applications of the binary trees/spanning trees. (5)

4. a) Illustrate how Euler’s formula for planar graphs can be used to examine the planarity of graphs. (5)

b) Use Kuratowski’s theorem to examine the following graph for planarity. (5)

5. a) Determine the bases of the circuit-subspace and the cut-set subspace of a vector space associated with graph G. (5)

b) State and establish a relationship between the circuit-subspace and the cut-set subspace of a vector space associated with graph G. (5)

6. a) Determine the rank of a circuit matrix of a connected graph G. (5)

b) Write down the cut-set matrix of the following graph. (5)

7. a) Determine the maximum number of edges that a simple graph with n vertices and k components can have. (5)

b) Describe two ways to implement trees in computer memory. (5)

8. a) Find the geometric dual of the following: (2.5+2.5)

i) a wheel Wn ii) dodecahedron graph

b) If X is the adjacency matrix of a graph G with n vertices , and

, (in the ring of integers), then G is disconnected if and only if there exists atleast one entry in matrix Y that is zero. (5)