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.

While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs. My question is what about the square of the cycles $C_n$? are they too minimal self-centered? I worked out on few examples. Somewhere it is and somewhere not. How to prove theoretically that squares of cycles $C_n$ are not minimal self-centered. A graph is said to be minimal if it loses its property if we remove any arbitrary edge.

share|improve this question
    
i got that if we square a cycle then degree of every vertex is 4, and if we remove 3 edges incident on a vertex then the square of cycle is not self-centered, as self-centered graphs contains no veretx of degree one. how to show that if we remove a single arbitrary edge, then square of cycles is not minimal self-centered. –  monalisa Mar 20 '13 at 7:00
    
What is "the square of the cycles"? –  Boris Novikov Mar 20 '13 at 7:49
    
@BorisNovikov 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. here is the link for details mathworld.wolfram.com/GraphPower.html –  monalisa Mar 20 '13 at 8:11
    
Nice question.${}{}{}$ –  Alexander Gruber Mar 22 '13 at 10:05
    
@monalisa Is it true that the square of the cycle is minimal self-centered for $n=6,7,8$ and not for $n=4,5,9$? –  Boris Novikov Mar 23 '13 at 15:03

1 Answer 1

up vote 2 down vote accepted
+50

For each cycle $C_n$, we label the vertices clockwise $v_1, v_2, ..., v_n$, and denote $e_{i,j}$ as the edge connecting the vertices $v_i, v_j$. Let the square of cycle $C_n$ be the graph $S_n$, with the same naming for the vertices.

Assume to the contrary that the graph $S_n$ is minimally self-centered. Since it is self-centered, the graph diameter and graph radius must be both equal to some integer $k$.

We first consider the case where $n\ge6$. For $n\ge6$, you can verify that $k\ge2$, since the $d(v_1, v_{\lfloor{n/2}\rfloor})\ge2$

Now, let us remove the edge $e_{1,2}$ between vertices $v_1, v_2$ to produce a graph $T_n$.

Lemma 1: In the graph $T_n$, the graph distance $d(v_i,v_j)$ between any two vertices is the same as that in $S_n$ if and only if $(v_i,v_j)\neq(v_1,v_2)$, and $d(v_1,v_2)=2$.

Proof: We can see this by noting that, if in $S_n$, the path of minimum length between $v_i, v_j$ passed through the edge $e_{1,2}$, then the path must include an edge $e_{a,1}$ or $e_{2,b}$ (or both), for otherwise the path is simply $e_{1,2}$ and must connect the vertices $v_1, v_2$.

  1. If the path contains the edge $e_{a,1}$, the edge must be $e_{n-1,1}$. (The path $e_{n,1}e_{1,2}$ cannot be part of any minimal path since $e_{n,2}$ would have been a shorter path. Edit: Also, as pointed out by @IvanLoh, the path $e_{3,1}e_{1,2}$ cannot be part of any minimal path since $e_{3,2}$ would have been a shorter path.) We can then change the segment of the path $e_{n-1,1}e_{1,2}$ to $e_{n-1,n}e_{n,2}$ with no change to the minimal path length.
  2. Similarly, if the path contains the edge $e_{2,b}$, the edge must be $e_{2,4}$. We can change the segment of the path $e_{1,2}e_{2,4}$ to $e_{1,3}e_{3,4}$.

By Lemma 1, since the graph distance between any two vertices other than $v_1,v_2$ remains the same, and $d(v_1,v_2)=2\le k$, the graph diameter and graph radius will not change either, and $T_n$ is also a self-centered graph, contradicting the assumption that $S_n$ is minimally self-centered.

It remains to check the cases where $n<6$, and this can be done easily by hand.

share|improve this answer
    
If I understand your question correctly, then your conjecture is not true for n=3,4,5. I'm not sure how to think of the cases n=1,2. –  Vincent Tjeng Mar 25 '13 at 4:46
1  
For your first case for lemma 1, you should probably also mention that $e_{3, 1}$ cannot be part of any minimal path. –  Ivan Loh Mar 26 '13 at 6:24

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.