Loyola College M.Sc. Mathematics Nov 2008 Algorithmic Graph Theory Question Paper PDF Download

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 35

M.Sc. DEGREE EXAMINATION – MATHEMATICS

THIRD SEMESTER – November 2008

    MT 3806 – ALGORITHMIC GRAPH THEORY

 

 

 

Date : 15-11-08                   Dept. No.                                          Max. : 100 Marks

Time : 1:00 – 4:00

Answer all questions. Each question carries 20 marks.

 

1(a)(i). Prove that an edge of a graph is a cut edge if and only if it is contained in no cycle

of the graph.

(OR)

(ii). Prove that an interval graph satisfies the triangulated graph property. Give an

example to show that not triangulated graph is an interval graph.                                                    (5)

 

(b) (i). Define connectivity and edge-connectivity with examples.

(ii). Prove that a graph G with  is 2-connected if and only if any two vertices of

G are connected by at least two internally-disjoint paths.                                                     (5+10)

 

(OR)

 

(iii). State the depth-first search algorithm and simulate it on the following graph by

selecting the vertex a.

(15)

2(a)(i). Define a simplicial vertex. Obtain a perfect elimination scheme for the following

graph.

(OR)

(ii). Define a vertex separator and a minimum vertex separator. Obtain a minimum

vertex separator for the following graph.

(5)

 

(b)(i). Let G be an undirected graph. Then prove that the following statements are

equivalent.

(1). G is triangulated.

(2). Every minimal vertex separator induces a complete subgraph in G.

(ii). State the Lexicographic breadth first search algorithm and apply it to the following

graph and obtain the perfect elimination scheme.

 

(OR)

 

(iii). Suppose that there is a tree T whose vertex set is the set of maximal cliques of a graph G such that each induced subgraph : v ε V is connected, where Kv consists of those maximal cliques which contain v. Prove that G is the intersection graph of a family of subtrees of a tree and hence deduce that G is triangulated.

 

(iv). Prove that a family of subtrees of a tree satisfies the Helly property.                                     (10+5)

 

  1. (a)(i). Define covering and edge-coverings in a graph with examples.

 

(OR)

 

(ii). Let G be a split graph with the vertex set partitioned into a stable set S and a

clique K. If |S| = α(G) and |K| = ω(G) – 1, then prove that there exists an x ε S

such that K +{x} is a clique.                                                                                                               (5)

 

(b)(i). Let G be an undirected graph. Prove that the following statements are equivalent.

(1). G is a split graph

(2). G and  are triangulated graphs

(3). G contains no induced subgraph isomorphic to 2K2, C4 or C5.                                      (15)

(OR)

 

(ii). Define a graphic sequence. Check whether the sequence (8, 8, 6, 5, 5, 4, 3, 3, 2)

is graphic.

(iii). Obtain a necessary and sufficient condition for a sequence to be graphic.                           (5+10)

 

  1. (a)(i). Define a vertex colouring and a critical graph. Prove that in a k-critical graph

the minimum degree of vertices is at least k – 1.

 

(OR)

 

(ii). What is a permutation labeling? Illustrate with an example.                                                           (5)

(b)(i). Prove that an undirected graph G is a permutation graph if and only if G and

are comparability graphs.                                                                                                         (15)

(OR)

 

(ii). Define a permutation graph. Draw the permutation graph corresponding to the

permutation [5,2,1,7,6,8,3,4].

(iii). Let G be an undirected graph. Prove with usual notations that a bijection L

from V to {1, 2, 3 … n} is a permutation labeling if and only if the mapping

,  is an injection.                                                              (5+10)

 

  1. (a)(i). Define a planar graph. Prove that the complete graph on 5 vertices is non-planar.

 

(OR)

 

(ii). Obtain an interval representation of the interval graph given below.

 

(5)

 

 

(b)(i). Let G be an undirected graph. Then prove that the following statements are

equivalent.

(1). G is an interval graph

(2). G contains no chordless 4-cycle and its complement  is a

comparability graph.

(3). The maximal cliques can be linearly ordered such that, for every

vertex v of  G the maximal cliques containing v occurs consecutively.

 

(OR)

(iii). Prove that an undirected graph G is a circular arc graph if and only if its

vertices can be circularly indexed v1.v2vn so that for all i and j

 

(15 marks)

 

Go To Main page

Latest Govt Job & Exam Updates:

View Full List ...

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur