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



Course: B.E EXTC   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.


    Complete the action items below to enter to win an iPad Mini from India Study Channel! in India Study Channel - Locker on LockerDome
    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

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

    
    
    
    

    Click the "Follow" button above to follow Tony John