El más pequeño $k$ -grafo regular de distancia unitaria

Question

Podemos crear $k$ -regulares de distancia unitaria utilizando una "construcción hipercúbica": tomando un $k-1$ -grafo regular de distancia unitaria, haciendo una copia y trasladándola una distancia unitaria que no sea paralela a ninguna de las aristas existentes, y conectando todos los vértices entre las dos copias ( fuente ).

Sin embargo, esto no es óptimo, teniendo en cuenta que en el $k=2$ caso utilizando nuestra construcción obtenemos un gráfico con aspecto de rombo mientras que el gráfico completo $K_3$ es óptima. El grafo de 3 cubos tiene 8 vértices, mientras que un grafo con aspecto de prisma triangular tiene 6 vértices. ¿Cuáles son los $k$ -¿Gráficos regulares de distancia unitaria?

Mi idea de que el $k=3$ el caso de seis vértices es óptimo: el caso de cuatro vértices es el grafo completo que no es un grafo de distancia unitaria, y el caso de cinco vértices no puede satisfacer el lema del apretón de manos.

Answer 1

Para 4, necesitas el Cuadrángulo Generalizado {2,1} en 9 puntos.

Por 5, Turno y copia GQ21 por 18 puntos.
Un grafo quíntico de distancia unitaria más pequeño podría ser el grafo de Clebsch, pero es probable que se pueda demostrar que no es de distancia unitaria.

Con 6 obtienes Hamming-{3,3} (27 puntos)

Answer 2

¿En qué espacio se encuentra? Si se encuentra en $\Bbb R^{k-1}$ o superior, puede utilizar un simplex normal. Eso es claramente mínimo.