Birla Institute of Technology (BIT Mesra) 2007 B.E OPTIMIZATION - exam paper

(C ) (II) is accurate but (I) is incorrect (D) Both (I) and (II) are incorrect.
25. Let G1 = K42, 41 and G2 = K45, 62. Then which graphs have a Hamiltonian path?
(A) both G1 and G2 (B) G1 but not G2
(C) G2 but not G1 (D) neither G1 nor G2.










26. For the weighted graph G in Figure 2, let x be the weight of a minimal spanning tree and y be the weight of a maximal spanning tree. Then
(A) x = 9, y = 26 (B) x = 9, y = 25
(C) x= 10, y = 26 (D) None of the above.
27. For the graph G in Figure 2, let S be a largest subset of V(G) which is both dominating as well as independent. Then
(A) S does not exist (B) |S| = 0
(C) |S| = two (D) None of the above.
28. For the graph G in Figure 2, if ?(G) denote the chromatic number of G and c(G) denotes the covering number of G then
(A) ?(G) = 3, c(G) =4 (B) ?(G) = 4, c(G) =4
(C) ?(G) = 3, c(G) =7 (D) None of the above.
29. For the radius r and diameter d of the unweighted graph G in Figure 2,
(A) r = 4, d = seven (B) r = 4, d = 8
(C) r =2, d = two (D) None of the above.
30. For the graph G in Figure 2, Let x denote the maximum number of vertex disjoint paths from A to H and y denote the maximum number of edge disjoint paths from A to H. Then
(A) x = 3, y= three (B) x = 4, y = 3
(C) x =3, y =4 (D) None of the above.



BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, PILANI
Ist SEMESTER 2007 - 08
COMPREHENSIVE exam (Descriptive Part)
Course Title: Graphs and Networks Max. Marks: 55
Course No.: AAOC C221 Date: 12.12.2007 Time: one hr 45 min.
Write all subparts of identical ques. together.

1. Show that a tree on n vertices has exactly n-1 edges. [8]
2. Show that if a simple graph on n vertices has more than edges then it is connected. Is there a disconnected graph which has exactly n vertices and exactly edges for a few n? If yes, draw such a graph for the lowest value of n; otherwise justify why there is no such graph. [7]
3. Find the Kirchhoff matrix for the subsequent graph G0 and indicate the corresponding order of vertices. Hence obtain the the number of unlabelled spanning trees of G0. [5]









4. (a) describe (i) a cut set (ii) edge connectivity ?(G) of a connected graph G.
(b) For a simple connected graph G having exactly n vertices and e edges, e ? n-1, show that .
(c ) Is there a simple connected graph G with five vertices and eight edges with ?(G) = 3? If it exists then draw such graph and prove its edge connectivity is 3, otherwise justify why it doesn’t exist. [2+3+5]
5. Is there a simple graph G having no isolated vertices with |V(G)| = 7, domination number ?(G) = four and covering number = 4? If it exists then draw such a graph and justify your answer, otherwise justify why it doesn’t exist. [7]
6. Let G be a simple graph on n vertices, ?G its complement and respectively denote the chromatic numbers of G and ?G. Show that . [5]
7. Show that if G is a simple planar graph with |V(G)| ? 17 then its complement is not planar. [4]
8. For the subsequent directed network with provided capacities, obtain the value of a maximal (s, t)-flow without constructing any (s, t)-flow. [9]

Earning:   Approval pending.