## Graph Theory and Combinatorics - Jun 2013

### 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)** i) Define a connected graph. Give an example of a connected graph G where removing any edge of G results in a disconnected graphs.

ii) Define complement of a graph. Find an example of a self-complementary graph on four vertices and one on five vertices.(6 marks)
**1 (b)** Find all (loop-free) non-isomorphic undirected graphs with four vertices. How many of these graphs are connected?(5 marks)
**1 (c)** Show that the following graphs in Fig Q1(c) are isomorphic:

(5 marks)
**1 (d)** How many different paths of length 2 are there in the undirected graph G in Fig. Q1(d)?

(4 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.(6 marks)
**2 (b)** Define Planar graph. Let G=(V, E) be a connected planar graph or multigraph with |V|=V and |E|=e. Let r be the number of region in the plane determined by a planar embedding 0+G. Then prove that v-e+r=2.(7 marks)
**2 (c)** i) Find the chromatic number of the complete bipartite graph K_{m,n} and a cycle, C_{n} on n vertices n≥3.

ii) Determine the chromatic polynomial for the graph G in Fig. Q2(c).

(7 marks)
**3 (a)** i) Prove that in every tree T=(V,E), |E|=|V|-1.

ii) Let F_{1}=(V_{1}, E_{1}) be a forest of seven trees, where |E_{1}|=40. What is |V_{1}|?(7 marks)
**3 (b)** Define: i) Spanning tree ii) Binary rooted tree. Find all the non-isomorphic spanning trees of the graph Fig. Q3(b).

(6 marks)
**3 (c)** Define prefix code. Obtain an optimal prefix code for the message ROAD IS GOOD. Indicate the code.(7 marks)
**4 (a)** Apply Dijkstra's algorithm to the digraph shown in Fig. Q4(a) and determine the shortest distance from vertex a to each of the other vertices in the graph.

(7 marks)
**4 (b)** Define the following with respect to graph: i) matching ii) a cut-set. Show that the graph in Fig. Q4(b) has a complete matching from V_{1} to V_{2}. Obtain two complete matching.

(7 marks)
**4 (c)** For the network shown below, find the capacities of all the cutsets between A and D, and hence determine the maximum flow between A and D.

(6 marks)
**5 (a)** How many arrangement of the letters in MISSISSIPPI have to consecutive S's?(5 marks)
**5 (b)** i) Find the coefficient of v^{2}w^{4}xz in the expansion of (3v+2w+x+y+z)^{8}

ii) How many distinct terms arise in the expansion in part (i)?(5 marks)
**5 (c)** How many positive integers n can we form using the digits 3,4,5,5,6,7 if we want n to exceed 5000000?(5 marks)
**5 (d)** A message is made up of 12 different symbols and is to be transmitted through a communication channel. In addition to the 12 symbols, the transmitter will also send a total of 45 blank spaces between the symbols, with at least three spaces between each pair of consecutive symbols. In how many ways the transmitter sends such message?(5 marks)
**6 (a)** In how many ways can the 26 letters of the alphabet be permuted so that none of the patterns spin, game, path or net occurs?(7 marks)
**6 (b)** Define derangement. In how many ways can each of 10 people select a left glove and a right glove out of a total of 10 pairs of gloves so that no person selects a matching pair of gloves?(6 marks)
**6 (c)** Five teachers T_{1}, T_{2}, T_{3}, T_{4}, T_{5} are to be made class teachers for five classes C_{1}, C_{2}, C_{3}, C_{4}, C_{5} one teacher for each class T_{1} and T_{2} do not wish to become the class teachers for C_{1} or C_{2}, T_{3} and T_{4} for C_{4} or C_{5} and T_{5} for C_{3} or C_{4} or C_{5}. In how many ways can the teacher be assigned the work?(7 marks)
**7 (a)** Find the generating function for the following sequences:

i) 1^{2}, 2^{2}, 3^{2}, 42, ......

ii) 0^{2}, 1^{2}, 2^{2}, 3^{2}, ......

ii) 0, 2, 6 12, 30, .....(6 marks)
**7 (b)** Use generating function to determine how many four element subset of S={1, 2, 3, ....., 15} contain to consecutive integers?(7 marks)
**7 (c)** Using exponential generating function, find the number of ways in which 4 of the letters in the words given below be arranged: i) ENGINE

ii) HAWAII(7 marks)
**8 (a)** The number of virus affected files in a system is 1000 (to star with) and this number increase 250% every two hours. Use a recurrence relation to determine the number of virus affected files in the system after one day.(5 marks)
**8 (b)** Solve the recurrence relation:

a_{n+2}-10a_{n+1}+21a_{n}=3n^{2}-2, n?0(7 marks)
**8 (c)** Using the generating function method, solve the recurrence relation,

a_{n}-3a_{n-1}=n, n≥1 given a_{0}=1(8 marks)