# to find the distance

i am trying to find the power graphs of cycles $C_n$ and then calculation of distances between vertices. for cycles $C_n$ we can find power graphs upto power greatest integer function of n/2. Square of $C_n$ yielding result that distance between any two vertices is same. my question is how to prove that distance between any two vertices is same on squaring cycles.

-
What's a power graph? How do you square a cycle? (Do you mean the Cartesian product of $C_n$ with itself?) –  Douglas S. Stones Feb 20 '13 at 19:49
@DouglasS.Stones Sir, The kth power of a graph G is a graph with the same set of vertices as G and an edge between two vertices iff there is a path of length at most k between them. its an operation on a graph. here is the link en.wikipedia.org/wiki/Graph_operations –  monalisa Feb 21 '13 at 4:13
@DouglasS.Stones thus squaring a cycle means we are making every vertex v adjacent to all those vertices whose distance is 2 with vertex v –  monalisa Feb 21 '13 at 4:19
@DouglasS.Stones The idea that came to my mind while proving is that for every vertex u there exists 2 vertices v and w such that d(u,v)= d(u,w)= 2,3,... except for the distance |_n/2_| (greatest int. func). for that, if n in Cn is even then there exists a unique vertex u' such that d(u,u') = |_n/2_|. and if n is odd there exist 2 vertices v' and w' such that d(u,v') = d(u,w') =|_n/2_| –  monalisa Feb 21 '13 at 4:31

Thanks for the description above; that clears it up. (The square of $C_n$ is a special case of a Cayley graph $\mathrm{Cay}(\mathbb{Z}_n,\{\pm 1,\pm 2\})$. Since the group here is the cyclic group $\mathbb{Z}_n$, this is also known as a circulant graph.)

Here's an example, shaded according to their distance from the top vertex:

It would be possible to find the distance between any two vertices in "$C_n$ squared" by induction. Firstly, we need to check the small cases, then assume $n \geq 5$. After which, the following proof will work:

1. Base case: Check $\mathrm{dist}(u,u+1)=0$, $\mathrm{dist}(u,u+1)=1$, $\mathrm{dist}(u,u+2)=1$, $\mathrm{dist}(u,u-1)=1$, $\mathrm{dist}(u,u-2)=1$, and prove that there are no other vertices of distance $\leq 1$.

2. Inductive step: for $k \in \{2,3,\ldots,\lfloor n/4 \rfloor-1\}$, prove that $\mathrm{dist}(u,u+2k-1)=k$, $\mathrm{dist}(u,u+2k)=k$, $\mathrm{dist}(u,u-2k+1)=k$, $\mathrm{dist}(u,u-2k)=k$, , and prove that there are no other vertices of distance $\leq k$. This part will be made easier using the following property:

• The distance between two distinct vertices $u$ and $v$ satisfies $$\mathrm{dist}(u,v)=1+\min_{v' \in N(v)} \mathrm{dist}(u,v')$$ where $N(v)$ denotes the set of vertices adjacent to $v$.
3. End case: In this problem, the number of vertices of distance $\lfloor n/4 \rfloor$ from $u$ can be $1,\ldots,4$, depending on the value of $n$. This needs to be accounted for separately. (This is simply a bookkeeping issue that could arise.)

• "...distance between any two vertices is same..." If this implies that all pairs of vertices $C_n$ and the square of $C_n$ have the same distance, then this is not true: e.g. when $n=5$, the square of $C_n$ has $4$ vertices of distance $1$. In fact, squaring any graph with an induced $3$-node path $uvw$ will decrease the distance between $u$ and $w$.