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 )
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 )
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).

### 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!

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email