¿El grafo más pequeño que es transitivo en los vértices pero no transitivo en los bordes ni invariante en las aristas?

Question

Tomemos cualquier grafo no dirigido $G$ . Decimos que $G$ es vértice-transitivo si para cada vértice $v,w$ existe un automorfismo en $G$ que mapea $v$ à $w$ . Decimos que $G$ es borde-transitivo si para cada arista $e,f$ existe un automorfismo en $G$ que mapea $e$ à $f$ . Decimos que $G$ es invariante de los bordes si para cada arista con extremos $v,w$ existe un automorfismo en $G$ que mapea $v$ à $w$ y mapas $w$ à $v$ .

Al ver estos tres tipos de simetría, me surgió una pregunta curiosa:

Pregunta : ¿Cuál es el menor $n$ tal que existe un grafo con $n$ vértices que sea transitivo en los vértices pero no transitivo en los bordes ni invariante en los giros de los bordes?

Lo mejor que se me ocurrió fue el cubo romo (imagen de aquí ):

Es claramente vértice-transitiva, ya que cada vértice es un vértice de un cuadrado. Tampoco es sensible a las aristas, ya que una arista entre dos triángulos no puede ser transformada por un automorfismo en una arista próxima a un cuadrado. Y no es invariante respecto a las aristas, ya que ningún automorfismo puede dar la vuelta a una arista que esté junto a un triángulo rodeado de triángulos.

Pero, ¿existe algún gráfico más pequeño con esta propiedad? Había encontrado el cubo desairado buscando a través de poliedros "bonitos" (para que sea fácil verificar la transitividad de los vértices), y no estoy seguro de si hay una forma mejor de encontrar este tipo de grafos.

Answer 1

Creo que el siguiente gráfico con $12$ vértices hace el trabajo, pero no sé si es mínimo.

Se trata básicamente de un (anti)prisma hexagonal con diagonales adicionales. Etiqueta los vértices $A_1$ , $A_2$ , $A_3$ , $A_4$ , $A_5$ , $A_6$ et $B_1$ , $B_2$ , $B_3$ , $B_4$ , $B_5$ , $B_6$ . Los bordes son $\{A_i, A_{i+1}\}$ , $\{B_i, B_{i+1}\}$ , $\{A_i, B_i\}$ , $\{A_i, B_{i+1}\}$ , $\{A_i, B_{i+3}\}$ donde los índices son modulo $6$ .

Este es un dibujo que se enrolla alrededor de un cilindro, uniendo los lados izquierdo y derecho.

No creo que este tipo de construcción pueda funcionar utilizando un prisma con menos caras sin introducir una simetría especular que lo haría invariante respecto a las aristas.

Answer 2

Para profundizar en las posibles combinaciones de estos tres tipos de simetría:

Obsérvese que la invariabilidad de las aristas implica la transitividad de los vértices para todos los grafos conexos, ya que dados dos vértices cualesquiera $U,V$ conectadas por un camino, podemos concatenar los automorfismos que llevan cada vértice de este camino al siguiente y producir un automorfismo que envía a $U$ à $V$ .

Sin embargo, las otras 6 combinaciones son posibles. Denotando la transitividad de los vértices por $V$ la transitividad de los bordes por $E$ y la flip-transitividad por $F$ :

• $V, E, F$ : Triángulo

• $V, E, \neg F$ : Gráfico Holt

• $V, \neg E, F$ : Tetraedro truncado

• $V, \neg E, \neg F$ : Snub cube, y las otras respuestas a esta pregunta

• $\neg V, E, \neg F$ : Gráficos de estrellas

• $\neg V, \neg E, \neg F$ : Cualquier gráfico asimétrico

(Tenga en cuenta que un gráfico simétrico no es más que un gráfico que satisface todas $V, E,$ et $F$ porque para enviar un arco a otro, enviamos la arista asociada a su objetivo y volteamos si es necesario).

Answer 3

Mi respuesta original a continuación era incorrecta, ese gráfico es invariante de la inversión de aristas. De hecho es un $3\times3$ toroide, del que no es difícil ver que tiene todos los automorfismos necesarios para ser invariante de la inclinación de los bordes. Ahora estoy bastante convencido de que no existe un grafo semejante con menos de $10$ vértices.

Respuesta antigua e incorrecta:

Creo que este gráfico sobre $9$ vértices es el ejemplo más pequeño:

Answer 4

Esta es una respuesta negativa: Quería probar la idea de Jaap sobre cómo tal vez obtener otros ejemplos de 12 vértices. La idea era añadir diagonales al tetraedro truncado o cuboctaedro . Al menos las instancias que probé fallaron, porque ambas daban el gráfico de aristas del icosedro.

tetraedro truncado:

cuboctaedro:

Quizá haya que añadir diagonales corporales en su lugar.