Problem Set 1: (Graphs and Distances in Graphs)
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
a. What is the degree of vertex: 8, 11, 3, and 12?
b. Find the distance between vertices 3 and 13; 8 and 12; 2 and 5.
c. What are the eccentricities of the vertices of this graph?
d. What are the valences of vertices 13; 5; 10; 2?
e. Which vertex (there may be more than one) of this graph has minimal eccentricity?
2. For the graph H below:
a. What is the valence of vertex 4?
b. What is the length of the shortest path from vertex 0 to 8?
c. Find a closed walk from vertex 0 which is not a trail or a path.
d. Find an open trail from vertex 1 which is not a path.
e. Find a path with a largest number of edges from vertex 0 to vertex 8.
Comments and definitions
A graph can have labels on its vertices or be label free.
A graph can have weights on its edges or there may be no weights indicated.
The weights might represent times, costs, or some other quantity.
The distance between two vertices in a graph without weights is the length of the shortest path (counting edges) between the two vertices.
The diameter of a graph (without weights on its edges) is the length of the longest path between two vertices of the graph. (When a graph has weights, the length of a path is not the number of edges in the path but the sum of the weights on the edges in the path.)
The eccentricity of a vertex v in a graph G (no weights) is the farthest that any vertex of G can be from v.