Coloring and Distance: Sheet F
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
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. 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.