Practice 3: Graph Theory
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. (When an edge is removed its endpoints remain in place. If vertex v is removed, v the edges attached to v are removed, but the other end vertex of the edge at v stays in place.) The removal of a cut vertex or bridge (cut edge) increases the number of components of a graph.
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: