CS453 Graph Theory Assignment 4

Description

1. Recall that the adjacency matrix of a simple graph 𝐺 with vertex set
{𝑣1, 𝑣2, … , 𝑣𝑛
} is the 𝑛 × 𝑛 matrix 𝐴 with entries
𝐴𝑖,𝑗 = {
1 𝑣𝑖
is adjacent to 𝑣𝑗
0 otherwise
A. Let 𝐾3,4 be the complete bipartite graph with vertices
{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣7
} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and
only if 𝑖 and 𝑗 have different parity (one of 𝑖 or 𝑗 is odd and the other is
even.) What does the adjacency matrix 𝐴 look like in this case?
B. Let 𝐾3,4 be the complete bipartite graph with vertices
{𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5, 𝑣6, 𝑣7
} and where vertices 𝑣𝑖 and 𝑣𝑗 are adjacent if and
only if (𝑖 ≤ 3 and 𝑗 ≥ 4) or (𝑖 ≥ 4 and 𝑗 ≤ 3). What does the adjacency
matrix 𝐴 look like in this case?
2. We let 𝐺 be a connected graph. For any vertex 𝑣 ∈ 𝑉, define its
eccentricity by the formula
ecc(𝑣) = max{𝐷(𝑢, 𝑣): 𝑢 ∈ 𝑉}.
This is the length of “longest among all shortest paths with 𝑣 as an
endpoint.”
a. Let 𝐺 be the graph drawn below. Label each vertex with its
eccentricity.
b. The diameter of a graph is the maximum among the eccentricities of
its vertices and the radius of a graph is the minimum among the
eccentricities of its vertices. For the graph 𝐺 drawn in part a, what is
its diameter and radius?
c. A central vertex is a vertex 𝑣 such that ecc(𝑣) = radius(𝐺). Which
of the vertices in the graph 𝐺 are central vertices?
d. A peripheral vertex is a vertex 𝑣 such that ecc(𝑣) = diameter(𝐺).
Which of the vertices in graph 𝐺 are peripheral vertices?
e. Explain why it is important for these definitions that 𝐺 be a
connected graph.
f. Show that for any connected graph 𝐻,
radius(𝐻) ≤ diameter(𝐻) ≤ 2 radius(𝐻).
One inequality is quite easy and the second can be handled
using a central vertex and the triangle inequality.
3. Recall that a bridge is an edge whose deletion increases the number of
components of a graph. Also, a link is another term for “non-bridge.”
a. In the graph 𝐺 (same as in problem 2a) below, which edges are
bridges and which edges are links?
b. If you delete all of the bridges, how many components remain?
c. Suppose, instead, you deleted links one at a time until the
remaining graph had no links. How many links could you delete
in this process?
4. Let 𝐺 be a graph and 𝑥 be a vertex of 𝐺. We say that 𝑢~𝑤 if
𝐷(𝑢, 𝑥) = 𝐷(𝑤, 𝑥). When we discuss trees, the equivalence classes
will be the levels of a tree.
a. Show that this relation is reflexive.
b. Show that this relation is symmetric.
c. Show that this relation is transitive.
d. Suppose 𝑥 has no loops and suppose 𝑢𝑥 is an edge. Briefly
describe the equivalence class [𝑢].