## Graph Theory and Combinatorics - Jun 2012

### Computer Science Engg. (Semester 4)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.
**1 (a)** Define and give an example for each of the following: -

i) Connected graph

ii) Spanning subgraph

ii) Complement of a graph(6 marks)
**1 (b)** Define isomorphism. Show that the following graphs are isomorphism.
(7 marks)
**1 (c)** In the graph given below find the number of paths from V_{1} V_{2}. How many of these paths have length 5.
(7 marks)
**2 (a)** Define Hamilton cycle. How many edge-disjoint Hamilton cycles exist in the complete graph with seven vertices? Also draw the graph to show these Hamilton cycles.(7 marks)
**2 (b)** Prove that Peterson graph is non-planar.(6 marks)
**2 (c)** Define chromatic number of a graph. Find the chromatic polynomial for the graph shown below and also find the chromatic number for the same.
(7 marks)
**3 (a)** Define and give an example for each of the following:

i) Rooted tree

ii) Complete binary tree

iii) Balanced tree(6 marks)
**3 (b)** Construct an optimal prefix code for the symbols a, o, q, u, y, z that occur with the frequencies 20, 28, 4, 17, 12, 7 respectively.(7 marks)
**3 (c)** Obtain the optimal prefix code for the message "ROAD IS GOOD". Indicate the code.(7 marks)
**4 (a)** For the network shown below, determine the maximum flow between the vertices A and D by identifying the cutset of minimum capacity.
(7 marks)
**4 (b)** State and prove max-flow and min-cut theorem.(6 marks)
**4 (c)** Apply PRIMS algorithm to determine a minimal spanning tree for the weighted graph shown below.

(7 marks)
**5 (a)** State and explain product rule of counting along with an example.(4 marks)
**5 (b)** Find the co-efficient of:

i) x^{9}y^{3} in the expansion of (2x-3y)^{12}

ii) x^{9} in the expansion (3x^{2} - 2/x)^{15}.(8 marks)
**5 (c)** i) From seven consonants and five vowels how many sets consisting of four different consonants and three different vowels can be formed.

ii) Find the number of arrangement of the letters in TALLAHASSEE which have no adjacent A's.(8 marks)
**6 (a)** Out of 30 students in hostel, 15 study history, 8 study economics and 6 study geography. It is know that 3 students all these subjects. Show that 7 or more students study none of these subjects,(6 marks)
**6 (b)** Find the number of derangements pf the integers from 1 to 2n satisfying the condition that the elements in the first n-places are:

i) 1, 2, 3, ......, n in some order

ii) n+1, n+2, ........., 2n in some order.(6 marks)
**6 (c)** What is the expansion formula for rook-polynomials? Find the rook polynomial for the 3×3 board by using the expansion formula.(8 marks)
**7 (a)** i) Find a generating function for the following sequence, 0^{2}, 1^{2}, 22, 3^{2} .......

ii) Find the co-efficient of x^{27} in the expansion of the following functions.

(x^{4}+2x^{5}+3x^{6}+......)^{5}.(6 marks)
**7 (b)** Using generating function, find the number of partitions of n=6.(7 marks)
**7 (c)** Define an exponential generating function. Find the exponential function for the number of ways to arrange n-letter n≥0, selected for each of the following words.

i) HAWAII

ii) MISSISSIPPI

iii) ISOMORPHISM(7 marks)
**8 (a)** Solve the recurrence relation (Fibonacci relation).

F_{n+2}=F_{n+1}+F_{n} given F_{0}=0 and F_{1}=1 and n≥0(6 marks)
**8 (b)** Solve the recurrence relation

a_{ n+3} -3a_{n+2} + 3a_{n+1} - a_{n}=3 +5n for n≥0(7 marks)
**8 (c)** Find a generating function for the recurrence relation

a_{n+2}-3a_{n+1}+2a_{n}=0, n≥0 and a_{0}=1, a_{1}=6. Hence solve it.(7 marks)