Middle East Technical University Fall 2001/2002 Math 341 Graph Theory

FINAL

JANUARY 21, TIME: 100 MIN

Name, Student Number, Signature: ——————————————————————————————————–

|  1  2  3  4  5  6  |  Σ  |

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

Problem 1. (10 pts) Sketch a generic immersed curve with the following Chord Diagram.

Problem 2. (15 pts) Prove that K_{5,5} has genus greater then 1 (i.e., cannot be sketched on a torus).

Problem 3. (20 pts) Consider a cubic graph G with 2n vertices. Prove that (1) If G is Hamiltonian, then its edges are 3-colorable.

(2) If the edges of G are 3-colorable, then α_{1} = β_{1} = n (α_{1} and β_{1} denote the edge covering and the edge independence numbers).

Problem 4. (20 pts)

(1) Finds a group G and a set of its elements C ⊂ G \ e so that the Cayley graph X(G, C) is isomorphic to K_{3,3}.

(2) Prove that X(G, C) can never be isomorphic K_{3,4}, whatever G and C we consider.

Problem 5. (30 pts) For the graph K_{3} × K_{3} (1) determine the number of vertices and edges;

(2) find the chromatic number;

(3) find the vertex independence number;

(4) find the edge covering number.

Problem 6. (36 pts) For the graph K_{3.4} (1) estimate the vertex connectivity;

(2) determine the edge chromatic number;

(3) estimate the edge connectivity;

(4) describe the orbits of the automorphism group action on the vertices;

(5) describe the stabilizers of the action of the above group on the vertices;

(6) determine the order of the automorphism group.

Typeset by AMS-TEX