Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
@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
add comment

1 Answer

up vote 1 down vote accepted

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:

$C_9$ and $C_9$ squared

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

Other comments:

  • "...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$.
share|improve this answer
    
@douglas.... thanks a lot sir...m trying now how to prove. your idea made it easy for me. thanks for timely help. –  monalisa Feb 28 '13 at 6:48
    
Sir, i got your idea explained in point 2., but unable to express it in words. theoretically i mean. –  monalisa Mar 11 '13 at 6:14
    
Point 2 essentially says that if P is a shortest path from u to v (when u and v are distinct), then P must go through a neighbour w of v (i.e. the path goes from u to w then to v). Moreover, P must be also contain a shortest path from u to w, otherwise if Q was a shorter path from u to w, then Qv is a path from u to v shorter than P, which is a contradiction. –  Douglas S. Stones Mar 11 '13 at 12:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.