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 M.Sc Mathematics 640. graph theory Dec. 2010 Annamali university Question paper



Course: M.Sc Mathematics   University/board: Annamalai University





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 self-complementary, 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 z-edge 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 k-critical, prove that d = k - 1
9. Prove that every planar graph is 6 – vertex colourable.
10. If G is 2-edge 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 m-connected. (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 4-chromatic, 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

Next Question Paper: B.Sc. DEGREE EXAMINATION - 2010 (BOTANY) / (SECOND YEAR) (PART – III) / (PAPER – I) 640. BRYOPHYTES, PTERIDOPHYTES, GYMNOSPERMS AND PALEOBOTANY

Previous Question Paper: After PUC - Paper III - August 2009

Related Question Papers:


  • B.Sc. DEGREE EXAMINATION, 2010 ( ELECTRONIC SCIENCE ) ( THIRD YEAR ) ( PART - III - MAIN ) ( PAPER - V ) 720. DIGITAL ELECTRONICS ( Including Lateral Entry )


  • B.Sc. DEGREE EXAMINATION, 2010 ( ELECTRONIC SCIENCE ) ( THIRD YEAR ) ( PART - III - A : MAIN ) ( PAPER - IV ) 710. ELECTRONIC CIRCUITS ( Including Lateral Entry )


  • B.Sc. DEGREE EXAMINATION, 2010 ( ELECTRONIC SCIENCE PHYSICS ) ( SECOND YEAR ) ( PART - III - B : ANCILLARY ) 660. COMPUTER AND ITS APPLICATIONS ( Including Lateral Entry )


  • B.Sc. DEGREE EXAMINATION, 2010 ( APPLIED CHEMISTRY / ELECTRIC SCIENCE / PHYSICS ) ( SECOND YEAR ) ( PART - III - B - ANCILLARY ) 660 / 650. MATHEMATICS - II


  • B.Sc. DEGREE EXAMINATION, 2010 ( ELECTRONIC SCIENCE ) ( SECOND YEAR ) ( PART - III - A : MAIN ) ( PAPER - III ) 640. MATERIAL PHYSICS AND SEMICONDUCTOR DEVICES ( Including Lateral Entry )


  • Categories


    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.

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.