número máximo de aristas que deben eliminarse para poseer una propiedad

Question

Estoy trabajando en un problema. Sabemos que en la cuadratura de un ciclo, el grado de cada vértice es 4. Para los cuadrados de ciclos, sabemos que si eliminamos cualquier arista arbitraria, la excentricidad sigue siendo la misma para todos los vértices. Y si suprimimos 3 aristas incidentes en un mismo vértice, pierde la propiedad de que la excentricidad es la misma para todos los vértices, porque la excentricidad no es la misma para aquellos grafos que tienen un vértice de grado1. Cómo averiguar el número máximo de aristas a eliminar para que la excentricidad siga siendo la misma. Cualquier idea o sugerencia será de gran ayuda. Gracias por vuestra ayuda.

Answer 1

La plaza $G$ de un gráfico de ciclo de longitud $n$ tiene vértices $0,1,\ldots, n-1$ y un borde entre $a$ et $b$ si $a-b\equiv -2, -1, 1, \text{ or }2\pmod n$ . Obsérvese que esto implica que la afirmación de que $\rho(a)=4$ para todos los vértices sólo se cumple si $n>4$ . Por lo tanto, en lo que sigue, supondremos que $n>4$ . Sea $F(n)$ sea el número mínimo de aristas que pueden eliminarse de forma que la propiedad de excentricidad de la misma de $G$ se destruye.

La distancia en $G$ de vértice $0$ al vértice $k$ es bastante obvio $d(0,k)=\min\{\lceil\frac k2\rceil,\lceil\frac {n-k}2\rceil\}$ y, por tanto, la excentricidad de $0$ est $\epsilon(0)=\left\lceil\frac{\lfloor \frac {n}2\rfloor}2\right\rceil=\lfloor\frac{n+2}4\rfloor$ (y por simetría para todos los vértices). Observamos lo siguiente sobre los caminos más cortos desde $0$ a $k$ :

• Todos los pasos van en el sentido de las agujas del reloj o todos van en sentido contrario. Esto se debe a que dos pasos consecutivos en sentido contrario se anulan o pueden sustituirse por un solo paso.
• Si $\lceil \frac k2\rceil=\lceil \frac {n-k}2\rceil$ existen caminos más cortos tanto en el sentido de las agujas del reloj como en sentido contrario.

Lema 0. Si $n\not\equiv 1\pmod 4$ entonces $F(n)>1$ .

Prueba: Sea $G^\star$ cualquier gráfico obtenido a partir de $G$ eliminando una arista. Dado que cada arista de $G$ es parte de un triángulo, $d^\star(v,w)\le d(v,w)+1$ . Por lo tanto, la excentricidad sólo puede cambiar si crece la distancia a los vértices más alejados. Para $v=0$ son los siguientes:

• Si $n=4m-2$ : $w=2m$ con una trayectoria de longitud $m$ en el sentido de las agujas del reloj y en sentido contrario
• Si $n=4m$ : $w=2m$ con un recorrido de longitud $m$ en el sentido de las agujas del reloj y en sentido contrario; $w=2m\pm1$ con un camino que comienza y otro que termina con una arista de longitud $1$
• Si $n=4m-1$ : $w=2m$ con una trayectoria de longitud $m$ en el sentido de las agujas del reloj (todos los pasos de longitud $2$ ) y varias trayectorias en sentido contrario a las agujas del reloj (con un paso de longitud $1$ ); $w=2m+1$ de forma similar.

En todos los casos, hay dos caminos de la longitud requerida, por lo que la distancia no cambia al eliminar una sola arista. $_\square$

Lema 1. Si $n\equiv 1\pmod 4$ entonces $F(n)=1$ .

Prueba: Supongamos que $n=4m+1$ (para que $\epsilon(v)=m$ ) y que $G'$ sea el gráfico $G$ con borde $(0, 2)$ eliminado. Claramente, $d'(1,v)=d(1,v)$ para todos $v$ y por lo tanto $\epsilon'(1)=\epsilon(1)$ . El único camino $0\stackrel 2\to2\stackrel 2\to\ldots\stackrel 2\to2m$ de longitud $m$ de $0$ a $2m$ no existe en $G'$ Por lo tanto $$\epsilon'(0)\ge d'(0,2m)>m=\epsilon(1).$$ La eliminación de una sola arista puede destruir la misma propiedad de excentricidad. $_\square$

Lema 2. Si $n\equiv 3\pmod 4$ entonces $F(n)=2$ .

Prueba: Sea $n=4m-1$ (para que $\epsilon(v)=m$ para todos $v$ ) y que $G''$ sea $G$ con bordes $(0,1)$ et $(0,2)$ eliminado. Entonces $$\epsilon''(0)\ge d''(0,2m-2)\ge \min\{d(n-1,2m-2),d(n-2,2m-2)\}+1=m+1$$ porque cualquier ruta desde $0$ debe tener $n-1$ o $n-2$ como siguiente nodo. Por otro lado, $d''(1,v)=d(1,v)$ a menos que todos los más cortos $G$ -caminos de $1$ a $v$ contienen $(0,1)$ o $(0,2)$ . Este último nunca es el caso y el primero sólo si $v=0$ (pero ese caso no importa ya que $d''(1,0)=2\le m$ ) ya que de lo contrario el camino más corto continúa $1\stackrel 1\to 0\stackrel 2\to n-2$ y puede sustituirse por $1\stackrel 2\to n-1\stackrel1\to n-2$ . Por lo tanto $\epsilon''(1)=\epsilon(1)=m$ . $_\square$

Lema 3. Si $n\equiv 0\pmod 4$ entonces $F(n)=2$ .

Prueba: Sea $n=4m$ (para que $\epsilon(v)=m$ ) y de nuevo $G''$ sea $G$ con bordes $(0,1)$ et $(0,2)$ eliminado. Entonces $$\epsilon''(0)\ge d''(0,2m-1)\ge \min\{d(n-1,2m-1),d(n-2,2m-1)\}+1=m+1$$ mientras que al igual que en el caso anterior $\epsilon''(1)=\epsilon(1)$ . $_\square$

Lema 4. Si $n\equiv 2\pmod 4$ entonces $F(n)=3$ .

Prueba: Sea $n=4m-2$ (así $\epsilon(v)=m$ ) con $m\ge 2$ y que $G^\star$ sea cualquier grafo obtenido eliminando dos aristas de $G$ . Demostraremos que $d^\star(0,v)\le m$ para $1\le v\le 2m-1$ . Entonces, por simetría tendremos $\epsilon^\star(v)=m$ para todos $v$ .

Para $v=2m-1$ Obsérvese que hay cuatro caminos de aristas disjuntas de longitud $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$ y lo mismo en sentido negativo. Como máximo dos de ellas pueden ser destruidas por la eliminación de aristas, por lo tanto $d^\star(0,v)=m$ .

Para $v=2m-2$ tenemos caminos de aristas disjuntas $0\stackrel2\to n-2\stackrel2\to\ldots\stackrel2 2m-2$ , $0\stackrel2\to2\stackrel2\to\ldots\stackrel2\to 2m-2$ et $0\stackrel 1\to1\stackrel2\to\ldots\stackrel1\to 2m-2$ de longitudes $\le m$ . Una vez más, hay que sobrevivir a la eliminación de los bordes, $d^\star(0,v)\le m$ .

Para $2<v<2m-2$ impar, tenemos dos caminos de aristas disjuntas $0\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ et $0\stackrel 2\to 2\stackrel 2\to\ldots\stackrel1\to v$ de longitud $<m$ . A menos que cada uno de estos caminos contenga exactamente una de las aristas eliminadas, hemos terminado. Si $(0,1)$ es una arista eliminada, entonces $0\stackrel 1n-1\to 2\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ tiene longitud $m$ (tenga en cuenta que $(1,2)\ne(v-1,v)$ y hemos terminado. Del mismo modo, hemos terminado si $(v-1,v)$ es una arista eliminada. Por lo tanto, podemos suponer que en cada uno de los dos caminos, una arista $(k,k+2)$ y que los bordes $(k,k+1)$ et $(k+1,k+2)$ están presentes en $G^\star$ de forma que obtengamos un camino de longitud $\le m$ .

Para $2\le v<2m-2$ par, tenemos dos caminos de aristas disjuntas $0\stackrel 1\to1\stackrel 2\to\ldots\stackrel1\to v$ et $0\stackrel 22\stackrel 2\to\ldots\stackrel2\to v$ de longitud $<m$ . De nuevo podemos suponer que falta exactamente una arista de cada camino. De nuevo, si $(0,1)$ podemos sustituirlo por $0\stackrel 1n-1\stackrel 21$ y, del mismo modo, si $(v-1,v)$ falta. De nuevo concluimos que en cada uno de los dos caminos, una arista $(k,k+2)$ y que los bordes $(k,k+1)$ et $(k+1,k+2)$ están presentes en $G^\star$ de forma que obtengamos un camino de longitud $\le m$ .

Para el caso restante $v=1$ Obsérvese que tenemos tres caminos de aristas disjuntas $0\stackrel 1\to 1$ , $0\stackrel 2\to 2\stackrel 1\to 1$ et $0\stackrel 1\to n -1\stackrel 2\to 1$ de longitud $\le 2\le m$ al menos uno de los cuales está presente en $G^\star$ . Junto con su propio resultado sobre tres aristas, se deduce la afirmación del lema. $_\square$

En resumen

Teorema. Sea $n>4$ . Entonces $$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}$$

Observación: Obsérvense los casos degenerados $F(4)=1$ et $F(3)=1$ .

Answer 2

Esto es lo que puedo decir con certeza

Sea $n\ge 5$ . El número máximo de aristas que pueden eliminarse de un ciclo cuadrado para que la excentricidad de cada vértice permanezca inalterada es de al menos $n-2-(n+2)\operatorname{mod}4$ .

Para demostrar que esto es cierto, daré un conjunto explícito de aristas eliminadas en cada caso. Etiquete los vértices consecutivos del ciclo $1,2,3,\ldots, n$ y llamaremos a una arista "exterior" si conecta vértices adyacentes en el ciclo, e "interior" si conecta vértices a una distancia de dos entre sí. La división en cuatro casos, según la clase de residuo de $n$ modulo $4$ podemos eliminar las siguientes aristas:

• $n\equiv 0\operatorname{mod}4$ : $n-6$ bordes exteriores y $2$ bordes interiores. Retire todos los bordes exteriores excepto los que conectan $(1,2),(2,3),(3,4),(\frac{n}{2}+1,\frac{n}{2}+2),(\frac{n}{2}+2,\frac{n}{2}+3),$ et $(\frac{n}{2}+3,\frac{n}{2}+4)$ . Retire los bordes interiores que conectan $(1,3)$ et $(\frac{n}{2}+2,\frac{n}{2}+4).$
• $n\equiv 1\operatorname{mod}4$ : $n-5$ bordes exteriores y $0$ bordes interiores. Retire todos los bordes exteriores excepto los que conectan $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ et $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$ . No quite ningún borde interior.
• $n\equiv 2\operatorname{mod}4$ : $n-4$ bordes exteriores y $2$ bordes interiores. Retire todos los bordes exteriores excepto los que conectan $(1,2),(2,3),(\frac{n}{2}+1,\frac{n}{2}+2),$ et $(\frac{n}{2}+2,\frac{n}{2}+3)$ . Retire los bordes interiores que conectan $(1,3)$ et $(\frac{n}{2}+1,\frac{n}{2}+3)$ .
• $n\equiv 3\operatorname{mod}4$ : $n-5$ bordes exteriores y $2$ bordes interiores. Retire todos los bordes exteriores excepto los que conectan $(1,2),(2,3),(3,4),(\frac{n+3}{2},\frac{n+3}{2}+1),$ et $(\frac{n+3}{2}+1,\frac{n+3}{2}+2)$ . Retire los bordes interiores que conectan $(1,3)$ et $(\frac{n+3}{2},\frac{n+3}{2}+2)$ .

Todo esto debería coincidir con la conjetura. Lo anterior se demuestra caso por caso por inducción. Obsérvese que los grafos restantes en todos los casos tienen dos huecos de aristas exteriores. En cada hueco, podemos añadir $2$ vértices y $2$ aristas de modo que la excentricidad de cada vértice se eleve en $1$ (nótese que la excentricidad de un ciclo al cuadrado con $n+4$ bordes es $1$ mayor que la excentricidad de un ciclo al cuadrado con $n$ bordes).

Lo difícil es deshacerse de las palabras "al menos" en la afirmación anterior. Se puede demostrar que cuando $n\equiv 1\operatorname{mod}4$ no podemos eliminar ninguna arista interior, y necesitamos al menos $5$ bordes exteriores para preservar la excentricidad. Esto establece el resultado para $n\equiv 1\operatorname{mod}4$ .

En $n\equiv 0\operatorname{mod}4$ podemos eliminar como máximo $2$ bordes interiores, pero no puedo mostrar que $6$ Los bordes exteriores son necesarios.

Los demás casos son aún más delicados. Tengo razones para creer que mi resultado es cierto en todos los casos, pero no puedo demostrarlo formalmente.