Graph Theory Practice 5

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York


email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

1. For each graph G below find G - v for every vertex of G and G - e for each edge e of G. For each vertex and edge of G state whether or not the vertex/edge is a cut vertex/bridge.

a.

b.

c.

2.

a. For each graph above, find the distance between vertex 0 and every other vertex of the graph.

b. For each graph above, find the distance between vertex 4 and all higher numbered vertices.

3. Definition: The vertex coloring number of a graph G is the minimum number of labels (colors) that can be assigned to the vertices of G so that two vertices joined by an edge get different labels.

The vertex coloring number of a graph is usually denoted by the Greek letter chi.

Find the vertex coloring number for all of the graphs drawn above.

4. Definition: If G is a connected graph, and v is any vertex of G, the eccentricity of v, denoted e(v) is the farthest distance that any vertex w of G can be from v. (e(v) is a non-negative integer.)

Find the eccentricity of each vertex in the tree below: