LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
|
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)
- (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)
- (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)
- (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.v2 …vn so that for all i and j
(15 marks)
Latest Govt Job & Exam Updates: