LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

CV 52

M.Sc. DEGREE EXAMINATION – MATHEMATICS

THIRD SEMESTER – APRIL 2007

MT 3806 – ALGORITHMIC GRAPH THEORY

 

 

Date & Time: 28/04/2007 / 9:00 – 12:00      Dept. No.                                                Max. : 100 Marks

 

 

 

Answer all questions.

 

1(a)(i). Define clique cover, stability number and chromatic number. Illustrate with

examples.

(OR)

(ii). What is an intersection graph? Explain with an example.

(5 marks)

(b)(i). Prove that the complement of an interval graph satisfies the transitive orientation

property.

(ii). Let  and . Then

prove that d is graphic if and only if  is graphic.

 

(OR)

 

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

(v). State the breadth-first search algorithm. Simulate it on the following graph

by selecting the vertex p.

 

(3+12 marks)

2(a)(i). Define a simplicial vertex, a vertex separator and a perfect vertex elimination

scheme. Illustrate with examples.

(OR)

(ii). Obtain a clique tree representation of the following graph.

(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). Prove that every triangulated graph has a simplicial vertex.                                            (10+5 marks)

(OR)

 

(iii). Prove that a family of subtrees of tree satisfies the Helly property.

(iv). Prove that an undirected graph is triangulated if and only if the ordering produced

by the Lexicographic breadth first search is a perfect vertex elimination scheme.          (5+10 marks)

 

 

3(a)(i). Define a split graph and give an example.

(OR)

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

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

S +{y} is stable.

(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 2K₂, C₄ or C₅.

(OR)

(ii). Let G be an undirected graph with degree sequence d₁ ≥ d₂ ≥ … ≥ d_n and let m =

max {i : d_i ≥ i – 1}. Then prove that G is a split graph if and only if

 

.

(15 marks)

 

4(a)(i). Define and determine the permutation graph corresponding to the permutation

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

(OR)

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

 

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

are comparability graphs.

(OR)

(ii). 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.                                            (15 marks)

 

5(a)(i). Define an interval graph with an example.

(OR)

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

 

 

(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  comparability graph.

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

the maximal cliques containing v occurs consecutively.

(OR)

(ii). An undirected graph G is a circular arc-graph if and only if its vertices can be circularly indexed v₁, v₂,…,v_n so that for all i and j

 

Go To Main page

 

Latest Govt Job & Exam Updates:

View Full List ...