para encontrar la distancia

Question

Estoy tratando de encontrar las gráficas de potencia de ciclos $C_n$ y cálculo de distancias entre los vértices. % de ciclos $C_n$podemos encontrar gráficos hasta poder mayor entero función potencia de n/2. Cuadrado de $C_n$ rendimiento resultado que distancia entre cualquier dos vértices es el mismo. mi pregunta es cómo probar que la distancia entre cualquier dos vértices es igual en cuadratura ciclos.

Answer 1

Gracias por la descripción anterior; que lo borra. (El cuadrado de $C_n$ es un caso especial de un grafo de Cayley $\mathrm{Cay}(\mathbb{Z}_n,\{\pm 1,\pm 2\})$. Desde el grupo de aquí es el grupo cíclico $\mathbb{Z}_n$, esto también es conocido como un circulantes gráfico.)

He aquí un ejemplo, a la sombra de acuerdo a su distancia desde el vértice superior:

Sería posible encontrar la distancia entre dos vértices en "$C_n$ al cuadrado" por inducción. En primer lugar, debemos comprobar que el pequeño de los casos, a continuación, supongamos $n \geq 5$. Después de lo cual, la siguiente prueba:

1. Caso Base: Verificación $\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$, y demostrar que no son otros que los vértices de distancia $\leq 1$.

2. Inductivo paso: para $k \in \{2,3,\ldots,\lfloor n/4 \rfloor-1\}$, demostrar que $\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$, , y demostrar que no son otros que los vértices de distancia $\leq k$. Esta parte será más fácil el uso de la siguiente propiedad:

   • La distancia entre dos vértices $u$ $v$ satisface $$\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. Final del caso: En este problema, el número de vértices de distancia$\lfloor n/4 \rfloor$$u$$1,\ldots,4$, dependiendo del valor de $n$. Esto debe contabilizarse por separado. (Esto es simplemente una contabilidad problema que pudiera surgir.)

Otros comentarios:

• "...la distancia entre dos vértices es el mismo..." Si esto implica que todos los pares de vértices $C_n$ y el cuadrado de $C_n$ tienen la misma distancia, entonces esto no es cierto: por ejemplo, cuando se $n=5$, el cuadrado de $C_n$ $4$ vértices de distancia $1$. De hecho, el cuadrado de cualquier gráfico con un inducida $3$-ruta de acceso del nodo $uvw$ va a disminuir la distancia entre el$u$$w$.