Download Model question papers & previous years question papers
Posted Date: 12 Dec 2011 Posted By:: smilee Member Level: Bronze Points: 5 (Rs. 1)

2010 Annamalai University Communication B.E EXTC 640. graph theory Dec. 2010 Annamali university Question paper
M.Sc. DEGREE EXAMINATION, 2010 ( MATHEMATICS ) ( SECOND YEAR ) ( PAPER  VII ) 230. GRAPH THEORY December ] [ Time : 3 Hours Maximum : 100 Marks PART – A ( 8 × 5 = 40 ) Answer any EIGHT questions. All questions carries equal marks. 1. Define complement of a graph. Draw Kc3,4.If G is selfcomplementary, prove that ? = 0, 1 (mod 4). 2. Prove that a vertex v of a tree is a cut vertex if and only if, d(v) > 1. 3. If G is simple and d = ?  2, prove that k = d. 4. If G has a Hamilton path, prove that w(G – S) =  S  + 1 for every proper subset S of V. 5. Prove that a' = ß for bipartite graphs. 6. If G is a connected graph that is not an odd cycle, prove that G has a zedge colouring in which both colours are represented at each vertex of degree at least two. 7. State and prove Schur's Theorem. 8. If G is kcritical, prove that d = k  1 9. Prove that every planar graph is 6 – vertex colourable. 10. If G is 2edge connected, prove that G has a disconnected orientation.
PART – B ( 3 × 20 = 60 ) Answer any THREE questions. All questions carries equal marks. 11. (a) Explain shortest path problem and describe Dijkstra's algorithm with flow chart. (12) (b) With usual notations, prove that t  Kn = nn–2 (8) 12. (a) Explain the construction of Hm,n and prove that it is mconnected. (8) (b) State and prove Chvatal's Theorem for Hamiltoniam graphs. (3+9) 13. (a) What is personal assignment problem. Explain a method to solve it (10) (b) If G is bipartite, prove that ?' = ? (10) 14. (a) State and prove Turan's Theorem. (12) (b) If G is 4chromatic, prove that G contains a subdivision of K4. (8). 15. (a) Describe planarity algorithm and illustrate with an example. (12) (b) Prove that a digraph D contains a directed path of length ? – 1. (8).
Attachments:
Return to question paper search


Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.