Problem Set 1: (Graphs and Distances in Graphs)

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.

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.