maximum number of edges to be removed to possess a property

Question

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all vertices. And if we delete 3 edges incident on a single vertex, it loses its property that eccentricity is same for all vertices, because eccentricity is not same for those graphs having a vertex of degree1. How to find out the maximum number of edges to be deleted so that eccentricity is still same. Any idea or suggestion will be helpful. Thanks for your help.

Answer 1

The square $G$ of a cycle graph of length $n$ has vertices $0,1,\ldots, n-1$ and an edge between $a$ and $b$ iff $a-b\equiv -2, -1, 1, \text{ or }2\pmod n$. Note that this implies that the claim that $\rho(a)=4$ for all vertices holds only if $n>4$. Therefore, in what follows, we shall assume that $n>4$. Let $F(n)$ be the minimum number of edges that can be removed such that the same-eccentricity-property of $G$ is destroyed.

The distance in $G$ from vertex $0$ to vertex $k$ is quite obviously $d(0,k)=\min\{\lceil\frac k2\rceil,\lceil\frac {n-k}2\rceil\}$ and hence the eccentricity of $0$ is $\epsilon(0)=\left\lceil\frac{\lfloor \frac {n}2\rfloor}2\right\rceil=\lfloor\frac{n+2}4\rfloor$ (and by symmetry for all vertices). We observe the following about shortest paths from $0$ to $k$:

• All steps go clockwise or all go counterclockwise. This is because two consecutive steps in opposite direction either cancel or can be replaced by a single step.
• If $\lceil \frac k2\rceil=\lceil \frac {n-k}2\rceil$, shortest paths of both clockwise and anticlockwise orientation exist.

Lemma 0. If $n\not\equiv 1\pmod 4$, then $F(n)>1$.

Proof: Let $G^\star$ be any graph obtained from $G$ by removing one edge. Since each edge in $G$ is part of a triangle, $d^\star(v,w)\le d(v,w)+1$. Therefore, eccentricity can only change if the distance to the farthest vertices grows. For $v=0$, those are as follows:

• If $n=4m-2$: $w=2m$ with a path of length $m$ clockwise and counterclockwise
• If $n=4m$: $w=2m$ with as path of length $m$ clockwise and counterclockwise; $w=2m\pm1$ with a path beginning and a path ending with an edge of length $1$
• If $n=4m-1$: $w=2m$ with a path of length $m$ clockwise (all steps of length $2$) and several paths counterclockwise (with one step of length $1$); $w=2m+1$ similarly.

In all cases, there are two edge-disjoint paths of the required length, hence the distance does not change when removing a single edge. $_\square$

Lemma 1. If $n\equiv 1\pmod 4$, then $F(n)=1$.

Proof: Assume $n=4m+1$ (so that $\epsilon(v)=m$) and let $G'$ be the graph $G$ with edge $(0, 2)$ removed. Clearly, $d'(1,v)=d(1,v)$ for all $v$ and hence $\epsilon'(1)=\epsilon(1)$. The only path $0\stackrel 2\to2\stackrel 2\to\ldots\stackrel 2\to2m$ of length $m$ from $0$ to $2m$ does not exist in $G'$, hence $$\epsilon'(0)\ge d'(0,2m)>m=\epsilon(1).$$ Removing a single edge can destroy the same-eccentricity-property. $_\square$

Lemma 2. If $n\equiv 3\pmod 4$, then $F(n)=2$.

Proof: Let $n=4m-1$ (so that $\epsilon(v)=m$ for all $v$) and let $G''$ be $G$ with edges $(0,1)$ and $(0,2)$ removed. Then $$\epsilon''(0)\ge d''(0,2m-2)\ge \min\{d(n-1,2m-2),d(n-2,2m-2)\}+1=m+1$$ because any path from $0$ must have $n-1$ or $n-2$ as next node. On the other hand, $d''(1,v)=d(1,v)$ unless all shortest $G$-paths from $1$ to $v$ contain either $(0,1)$ or $(0,2)$. The latter is never the case and the former only if $v=0$ (but that case does not matter as $d''(1,0)=2\le m$) as otherwise the shortest path continues $1\stackrel 1\to 0\stackrel 2\to n-2$ and can be replaced with $1\stackrel 2\to n-1\stackrel1\to n-2$. Hence $\epsilon''(1)=\epsilon(1)=m$. $_\square$

Lemma 3. If $n\equiv 0\pmod 4$, then $F(n)=2$.

Proof: Let $n=4m$ (so that $\epsilon(v)=m$) and again let $G''$ be $G$ with edges $(0,1)$ and $(0,2)$ removed. Then $$\epsilon''(0)\ge d''(0,2m-1)\ge \min\{d(n-1,2m-1),d(n-2,2m-1)\}+1=m+1$$ whereas just as above $\epsilon''(1)=\epsilon(1)$. $_\square$

Lemma 4. If $n\equiv 2\pmod 4$, then $F(n)=3$.

Proof: Let $n=4m-2$ (so $\epsilon(v)=m$) with $m\ge 2$ and let $G^\star$ be any graph obtained by removing two edges from $G$. We will show that $d^\star(0,v)\le m$ for $1\le v\le 2m-1$. Then by symmetry we will have $\epsilon^\star(v)=m$ for all $v$.

For $v=2m-1$, note that there are four edge-disjoint paths of length $m$: $0\stackrel 1\to 1\stackrel2\to\ldots\stackrel2\to 2m-1$, $0\stackrel 2\to 2\stackrel2\to\ldots\stackrel2\to 2m-2\stackrel1\to 2m-1$, ans similarly in negative direction. At most two of these can be destroyed by the edge removal, hence $d^\star(0,v)=m$.

For $v=2m-2$, we have edge-disjoint paths $0\stackrel2\to n-2\stackrel2\to\ldots\stackrel2 2m-2$, $0\stackrel2\to2\stackrel2\to\ldots\stackrel2\to 2m-2$ and $0\stackrel 1\to1\stackrel2\to\ldots\stackrel1\to 2m-2$ of lengths $\le m$. Again, one must survive the edge removal, $d^\star(0,v)\le m$.

For $2<v<2m-2$ odd, we have two edge-disjoint paths $0\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ and $0\stackrel 2\to 2\stackrel 2\to\ldots\stackrel1\to v$ of length $<m$. Unless each of these paths contains exactly one of the removed edges, we are done. If $(0,1)$ is a removed edge, then $0\stackrel 1n-1\to 2\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ has length $m$ (note that $(1,2)\ne(v-1,v)$ and we are done. Similarly, we are done if $(v-1,v)$ is a removed edge. Therefore, we may assume that in each of the two paths, an edge $(k,k+2)$ is removed and that edges $(k,k+1)$ and $(k+1,k+2)$ are both present in $G^\star$ so that we obtain a path of length $\le m$.

For $2\le v<2m-2$ even, we have two edge-disjoint paths $0\stackrel 1\to1\stackrel 2\to\ldots\stackrel1\to v$ and $0\stackrel 22\stackrel 2\to\ldots\stackrel2\to v$ of length $<m$. Again we may assume that exactly one edge of each path is missing. Again, if $(0,1)$ is removed, we can replace it with $0\stackrel 1n-1\stackrel 21$ andsimilarly if $(v-1,v)$ is missing. Again we conclude that in each of the two paths, an edge $(k,k+2)$ is removed and that edges $(k,k+1)$ and $(k+1,k+2)$ are both present in $G^\star$ so that we obtain a path of length $\le m$.

For the remaining case $v=1$, note that we have three edge-disjoint paths $0\stackrel 1\to 1$, $0\stackrel 2\to 2\stackrel 1\to 1$ and $0\stackrel 1\to n -1\stackrel 2\to 1$ of length $\le 2\le m$, at least one of which is present in $G^\star$. Together with your own result about three edges, the claim of the lemma follows. $_\square$

In summary, we have therefore

Theorem. Let $n>4$. Then $$F(n)=\begin{cases}2 & \text{if }n\equiv 0\pmod 4\\1 & \text{if }n\equiv 1\pmod 4\\3 & \text{if }n\equiv 2\pmod 4\\2 & \text{if }n\equiv 3\pmod 4\\\end{cases}$$

Remark: Note the degenerate cases $F(4)=1$ and $F(3)=1$.

Answer 2

Here is what I can say with certainty

Let $n\ge 5$. The maximum number of edges that can be removed from a squared cycle so that the eccentricity of each vertex remains unchanged is at least $n-2-(n+2)\operatorname{mod}4$.

To show this is true, I will give an explicit set of removed edges in each case. Label consecutive vertices of the cycle $1,2,3,\ldots, n$ and call an edge 'outer' if it connects adjacent vertices in the cycle, and 'inner' if it connects vertices a distance of two from each other. Splitting into four cases, depending on the residue class of $n$ modulo $4$, we can remove the following edges:

• $n\equiv 0\operatorname{mod}4$: $n-6$ outer edges and $2$ inner edges. Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n}{2}+1,\frac{n}{2}+2),(\frac{n}{2}+2,\frac{n}{2}+3),$ and $(\frac{n}{2}+3,\frac{n}{2}+4)$. Remove inner edges connecting $(1,3)$ and $(\frac{n}{2}+2,\frac{n}{2}+4).$
• $n\equiv 1\operatorname{mod}4$: $n-5$ outer edges and $0$ inner edges. Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ and $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$. Remove no inner edges.
• $n\equiv 2\operatorname{mod}4$: $n-4$ outer edges and $2$ inner edges. Remove all outer edges except those connecting $(1,2),(2,3),(\frac{n}{2}+1,\frac{n}{2}+2),$ and $(\frac{n}{2}+2,\frac{n}{2}+3)$. Remove inner edges connecting $(1,3)$ and $(\frac{n}{2}+1,\frac{n}{2}+3)$.
• $n\equiv 3\operatorname{mod}4$: $n-5$ outer edges and $2$ inner edges. Remove all outer edges except those connecting $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ and $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$. Remove inner edges connecting $(1,3)$ and $(\frac{n+3}{2},\frac{n+3}{2}+2)$.

This should all match up with the conjecture. The above is proved case-by-case by induction. Notice that the remaining graphs in all cases have two gaps of outer edges. In each gap, we can add $2$ vertices and $2$ edges so that the eccentricity of each vertex is raised by $1$ (note that the eccentricity of a squared cycle with $n+4$ edges is $1$ greater than the eccentricity of a squared cycle with $n$ edges).

The hard part is getting rid of the words 'at least' in the above claim. It can be shown that when $n\equiv 1\operatorname{mod}4$, we cannot remove any inner edges, and we need at least $5$ outer edges to preserve eccentricity. This establishes the result for $n\equiv 1\operatorname{mod}4$.

When $n\equiv 0\operatorname{mod}4$, we can remove at most $2$ inner edges, but I can't seem to show that $6$ outer edges are necessary.

The other cases are even trickier. I have reason to believe my result is true for all cases, but a formal proof eludes me.