Considere la siguiente propiedad del gráfico: para cada $u, v \in V(G)$ tenemos que $G - u \cong G-v$ . Esta propiedad implica una alta "simetría" del gráfico.
Podemos ver fácilmente que cada gráfico de vértice-transitivo tiene esta propiedad. Mi pregunta: ¿es cierto lo contrario?
He intentado crear un contra-ejemplo pero hasta ahora no he encontrado ninguno. Agradezco cualquier respuesta, orientación o referencia. ¡Gracias de antemano!
En el caso finito, lo contrario es cierto. El truco es notar que todas las subgrafías $G \setminus u$ son isomórficas, entonces $G$ debe ser regular, digamos con valentía $k$ . Por lo tanto, los vecinos de $u$ en $G$ son precisamente los vértices de grado $k-1$ en $G \setminus u$ . Se deduce que cualquier isomorfismo de $G \setminus u$ a $G \setminus v$ debe mapear los vértices de $G \setminus u$ adyacente a $u$ (en $G$ ) a los vértices de $G \setminus v$ adyacente a $v$ b (en $G$ ). Dado esto, no es difícil mostrar que cada isomorfismo de $G \setminus u$ a $G \setminus v$ se extiende a un automorfismo de $G$ que mapea $u$ a $v$ .
Edición: Carsten Thomassen (JCT B, vol 43) demostró que un gráfico de vértices finitos localmente sin vértices aislados es un vértice transitivo si y sólo si sus subgráficos borrados de vértices son todos isomórficos.
Respuesta parcial:
Encontré un contra-ejemplo infinito, pero contable. Imaginen una suma desarticulada de infinitas copias de $K_1$ y $K_2$ es decir.., $$ \biguplus_ {n \in \mathbb {N}}(K_1 \uplus K_2).$$
Entonces, si eliminas cualquier vértice, el gráfico sigue siendo isomorfo a sí mismo ( $K_2$ se convierte en $K_1$ mientras que $K_1$ simplemente desaparece). Sin embargo, no hay ningún automorfismo que conecte los vértices pertenecientes a $K_1$ y $K_2$ .
Espero que esto ayude $ \ddot\smile $
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
