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

 

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

XZ 45

M.Sc. DEGREE EXAMINATION – MATHEMATICS

THIRD SEMESTER – APRIL 2008

    MT 3806 – ALGORITHMIC GRAPH THEORY

 

 

 

Date : 03/05/2008            Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

Answer all questions.

1(a)(i). Obtain clique covers of size 2 and 3 for the following graph.

(OR)

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

(5 marks)

(b)(i). State the breadth-first search algorithm. Simulate it on the following graph by  selecting the vertex a.

(ii). State the depth-first search algorithm and simulate it on the following graph by  selecting the vertex a.

(15 marks)

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

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

(OR)

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

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

(10+5 marks)

 

3(a)(i). Define a split graph; prove that an undirected graph is a split graph if and only if its complement is a               split graph.

(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 marks)

(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 a permutation graph. Draw the permutation graph corresponding to the

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

(OR)

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

(5 marks)

 

(b)(i). Prove that an undirected graph G is a 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 a circular arc graph. Illustrate with an example.

(OR)

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

 

(5 marks)

(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 v₁.v₂ …v_n so that for all i and j

 

(15 marks)

 

Go To Main page

 

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

 

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

 

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

 

5. (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 v₁.v₂ …v_n so that for all i and j

 

(15 marks)

 

Go To Main page