Sec 11.1 /3

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...