Sec 11.1 /6
6. If a, b are distinct vertices in a connected undirected graph
G, the distance from a to b is defined to be the length of a shortest
path from a to b (when a =b the distance is defined to be 0).
For the graph in Fig. 11.9, find the distances from d to (each
of) the other vertices in G.
Sec 11.1 /8
Figure 11.10 shows an undirected graph representing a section
of a department store. The vertices indicate where cashiers
are located; the edges denote unblocked aisles between cashiers.
The department store wants to set up a security system where
(plainclothes) guards are placed at certain cashier locations so
that each cashier either has a guard at his or her location or is
only one aisle away from a cashier who has a guard. What is
the smallest number of guards needed?
a b c
Sec 11.1 /11
10. Give an example of a connected graph G where removing
any edge of G results in a disconnected graph.
11. Let G be a graph that satisfies the condition in Exercise 10.
(a) Must G be loop-free? (b) Could G be a multigraph? (c) If
G has n vertices, can we determine how many edges it has?
Sec 11.1 /15
15. For the undirected graph in Fig. 11.12, find and solve a recurrence
relation for the number of closed v-v walks of length
n ≥ 1, if we allow such a walk, in this case, to contain or consist
of one or more loops.
Sec 11.1 /16
16. Unit-Interval Graphs. For n ≥ 1, we start with n closed intervals
of unit length and draw the corresponding unit-interval
graph on n vertices, as shown in Fig. 11.13. In part (a) of the
figure we have one unit interval. This corresponds to the single
vertex u; both the interval and the unit-interval graph can be
represented by the binary sequence 01. In parts (b), (c) of the
figure we have the two unit-interval graphs determined by two
unit intervals. When two unit...