next up previous
Next: Adjacency matrix (vertex matrix) Up: Definitions Previous: Connected Graphs

r-step connection

If $ P_i \rightarrow P_j $ holds, we say there is one step connection from $ P_i $ to $ P_j $. If $P_i \rightarrow P_k \rightarrow P_j$ holds, we say there is a two step connection from $ P_i $ to $ P_j $. Similarly, if $P_i \rightarrow P_{k_1} \rightarrow P_{k_2} \rightarrow \dots \rightarrow
P_{k_{r-1}} \rightarrow P_j$ holds we say there is an r-step connection from $ P_i $ to $ P_j $. In other words, if there is a path of length r from $ P_i $ to $ P_j $, we say, there is an r-step connection from $ P_i $ to $ P_j $. Notice that we are assuming all the connections have the same unit length.
Consider the following graph

\includegraphics[width=4in]{GT_fig_12.eps}

Figure 12

In the graph given above since $P_1 \rightarrow P_2$ holds,there is a one step connection from $ P_1 $ to $P_2$. Also, there is a one step connection from $ P_3 $ to $ P_1 $, and so on. There are 2-step connection from $P_4$ to $P_2$, $ P_1 $ to $P_4$, and $ P_3 $ to $P_2$, ...



Ali A. Daddel 2000-09-17