Middle East Technical University Fall 2001 Math 341 Graph Theory

MIDTERM EXAM II, PART II

DECEMBER 1, TIME: 90 MIN

Name, ID, signature: ——————————————————————————————————–

|  1  2  3  4  5  |  Σ  |

——————————————————————————————————–

Problem 1. (13 pts) Show (a) the cutpoints (b) the bridges (c) the blocks in the following graph. (d) Is this graph non-separable ?

Problem 2. (14 pts) (a) Represent graphs K_{1,4} and K_{2,3} as intersection graphs (i.e., describe a suitable set S and give a family F = {S_{1}, S_{2}, … } of its subsets representing the vertices of the graphs).

(b) Evaluate the intersection numbers of these graphs.

Problem 3. (17 pts) Consider graphs G_{1} and G_{2} below.

(1) Show how one can obtain G_{2} and G_{2} from more simple graphs using operations of product and join of graphs.

(2) Find the incidence matrix for G_{2}.

(3) Find the adjacency matrix for G_{2}.

Problem 4. (16 pts) For the graphs G_{1} and G_{2} of Problem 3 determine (1) the point covering number;

(2) the edge covering number;

(3) the point independence number

(4) the edge independence number.

Problem 5. (20 pts) For the graphs G_{1} and G_{2} of Problem 3 (1) determine the cycle ranks of G_{1} and G_{2};

(2) sketch a spanning tree and a cotree;

(3) write a basis for the cycle space of G_{2}.

Typeset by AMS-TEX