¿Qué gráfico es este?

Question

Para mi juego estoy tratando de implementar un mundo continuo mediante la interconexión de los nodos como el siguiente

Le pido perdón por mis malos dibujos

No sé cómo explicarlo pero NO ES UN GRÁFICO DENSO

Es la representación de 3x3 nodos Donde cada nodo está conectado al nodo adyacente vertical o diagonalmente (aristas en color turquesa)

Ex:

1-2, 1-4 2-1,2-3,2-5 5-2, 5-6, 5-4, 5-8

Ahora hay algunos bordes (coloreados en azul y púrpura)

1-7, 1-3 4-6 2-8

Necesito bordes como este para crear un mundo interminable/continuo para mi juego

Mi mundo es en realidad mucho más grande que esto, pero hice 3x3 por el bien del dibujo.

¿Hay algún nombre para este tipo de gráfico?

Answer 1

@Johannes Kloos tiene razón. El gráfico de la imagen es simplemente el producto cartesiano de $C_3$ con ella misma. Creo que en general te interesa el producto cartesiano de $C_k$ y $C_l$ .

Answer 2

"Donde cada nodo está conectado al nodo adyacente vertical o diagonalmente"

A juzgar por la imagen, debería decir horizontalmente en lugar de diagonalmente. Y si los vértices están conectados a cada vértice vertical y horizontalmente, la respuesta de fidbc es correcta para el $3 \times 3$ caso, pero no en general.

Si lo anterior es correcto, este gráfico se conoce como $3 \times 3$ gráfico de rook . Generalizando esto a la $k \times n$ caso, es el Producto cartesiano de $K_k$ y $K_n$ y el gráfico de líneas del grafo bipartito completo $K_{k,n}$ .

Si $n \geq k$ , entonces el número de $n$ -colores de la $k \times n$ El gráfico de la torre es el número de Rectángulos latinos de orden $n$ . En particular, el número de $n$ -colores de la $n \times n$ El gráfico de la torre es el número de Cuadros latinos de orden $n$ . Además, el polinomio cromático de este gráfico cuenta una generalización de los rectángulos latinos.

Este gráfico lo analizo en mi documento sobre la encuesta Las numerosas fórmulas para el número de rectángulos latinos .