E E1199 Pages: 5

Reg No.:_ Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
V SEMESTER B.TECH DEGREE EXAMINATION(S), MAY 2019

Course Code: CS309
Course Name: GRAPH THEORY AND COMBINATORICS

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries3 marks. Marks
1 Print a Walk, trail, path and cycle on the graph below. 3

(5)
(~ 2) ( )
¬ ` ल~ टन
C3) > ಹೋತಿ

2 Define pendant vertex, isolated vertex and null graph with an example each. 3
3 State travelling salesman problem. Print a travelling salesman’s tour on the graph 3
below.

4 Prove Dirac’s theorem for Hamiltonicity. 3
PART 0

Answer any two full questions, each carries9 marks.

5 9) Define isomorphism of graphs. Show that the graphs (a) and (b) are isomorphic. 4

Page 1 5