LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

AA 26

THIRD SEMESTER – NOV 2006

MT 3806 – ALGORITHMIC GRAPH THEORY

 

 

Date & Time : 01-11-2006/9.00-12.00   Dept. No.                                                       Max. : 100 Marks

 

 

Answer all questions.

 

1(a)(i). Define a graph and reversal of a graph with examples. What do you mean by

symmetric closure?

(OR)

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

graphic.

(5 marks)

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

property.

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

selecting the vertex a.

 

 

(OR)

 

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

 

(iv). Obtain a necessary and sufficient condition for a sequence to be

graphic.                                                                                               (3+12 marks)

 

2(a)(i). Define a triangulated graph, a simplicial vertex and a vertex separator with

examples.

(OR)

(ii). What is a perfect vertex elimination scheme? Obtain the same 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.

(10+5 marks)

(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). Apply the above algorithm for the following graph.

 

(5+10 marks)

 

 

3(a)(i). Define a split graph. Give an example of two non isomorphic split graphs with the

same degree sequence.

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

 

(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 [5,6,1,2,4,3,7].

(OR)

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

 

(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 a circular arc graph.

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

 

(OR)

 

(ii). Define circular 1’s property. Prove that a matrix M has circular 1’s property if and

only if M’ has consecutive 1’s property.

(iii). Prove that an m x n (0, 1) with nonzero entries can be tested for the circulars 1’s

property in O(m+ n +f) steps.                                                                (8+7 marks)

 

 

Go To Main Page

 

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

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

SECOND SEMESTER – APRIL 2012

MT 2813 – ALGORITHMIC GRAPH THEORY

 

 

Date : 24-04-2012             Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

Answer all questions. Each question carries 20 marks.

 

1. (a) Prove that every nontrivial loopless connected graph has at least two vertices that are

not cut vertices.                                                                                                    (5)

(OR)

 

• Define walk, trail, path, cycle and tree with examples. (5)

 

• (i) Prove that a connected graph is a tree if and only if every edge is a cut edge.

(ii)  State Dijkstra’s algorithm and use it to find the shortest distance between the vertices A and H in the weighted graph given below.                                      (5+10)

(OR)

• (i) Find a Hamiltonian path or a Hamiltonian cycle if it exists in each of the graphs given below. If it does not exist, explain why?
• Prove that an edge e of G is a cut edge of G if and only if e is contained in no cycle of G.                                                                         (6+9)

2. (a) Define the connectivity and edge connectivity of a graph G and give an example of a graph G in which k(G) < k¢ (G) < d (G).                                                                   (5)

 

(OR)

 

(b)  Prove that K₅ is non-planar.                                                                                  (5)

 

(c)  Define Eulerian graph. State and prove a necessary and sufficient condition for a graph to be Eulerian.                                                                                          (15)

(OR)

 

• Explain Chinese Postman problem. Use Fleury’s algorithm to find the Euler tour for the following graph.

(15)

 

3. (a) Define and obtain a minimal vertex separator for b and g.

 

(5)

(OR)

(b)  State the Lexicographic breadth first search algorithm.                                       (5)

 

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

(i) G is triangulated.

(ii) G is the intersection graph of a family of subtrees of a tree.

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

(OR)

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

(ii) 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 of G.                                                                                                                                                        (6+9)

 

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

(OR)

(b) Define a permutation graph. Draw the permutation graph corresponding to the permutation [9, 7, 1, 5, 2, 6, 3, 4, 8].                                                              (5)

 

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

(OR)

(d)      (i) Prove that an undirected graph G is a permutation graph if and only if G and  are comparability graphs.

(ii) Obtain the permutation from the following transitive orientations of G and.

(8+7)

 

5. (a) State the depth-first search algorithm.                                                                  (5)

(OR)

(b)  Obtain an interval representation for the following interval graph.

(5)

 

(c)  State the breadth-first search algorithm and simulate it on the following graph by

selecting the vertex a.

(OR)

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

 

Go To Main page