# finding the minimal property of a graph

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.

-
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

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.

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