Coloring and Distance: Sheet F

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 7 and every other vertex of the graph. (The distance between two vertices in a graph is the number of edges in as short a path as possible between the vertices.)

b. For each graph above, find the distance between vertex 5 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:

Definition: The central vertices of a connected graph are those vertices of the graph with minimum (smallest) eccentricity.

5. Find the centers of the graphs in 4. and 1a above.