Moviéndose a través de productos cartesianos, coronas y uniones en posición general

Información Básica

• ID del Artículo: 2505.00535
• Título: Moviéndose a través de productos cartesianos, coronas y uniones en posición general
• Autores: Sandi Klavžar, Aditi Krishnakumar, Dorota Kuziak, Ethan Shallcross, James Tuite, Ismael G. Yero
• Clasificación: math.CO (Matemática Combinatoria)
• Fecha de Publicación: 16 de octubre de 2025 (versión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2505.00535

Resumen

El problema de posición general requiere encontrar conjuntos grandes de vértices tales que ningún trío de vértices en el conjunto se encuentre en el mismo camino más corto. Recientemente se definió una versión dinámica de este problema, denominada problema de posición general en movimiento, en el cual un conjunto de robots debe visitar todos los vértices del grafo mientras mantiene la posición general. Este artículo estudia este problema en el contexto de productos cartesianos, coronas y uniones, proporcionando cotas superiores e inferiores para grafos generales así como valores exactos para familias de grafos que incluyen mallas, cilindros, grafos de Hamming y prismas de árboles.

Antecedentes de Investigación y Motivación

Origen del Problema

1. Problema estático de posición general: Originado en el acertijo geométrico de Dudeney, requiere encontrar el conjunto máximo de vértices en un grafo tal que ningún trío de vértices se encuentre en el mismo camino más corto
2. Aplicaciones en comunicación de robots: Suponiendo que los robots envían señales a través de caminos más cortos para comunicarse, para evitar interferencias en la comunicación, es necesario asegurar que ningún robot se encuentre en el camino más corto entre otros dos robots
3. Requisitos dinámicos: En el mundo real, la navegación de robots es dinámica y requiere movimiento dentro de la red, lo que motiva a los investigadores a considerar la versión móvil del problema de posición general

Significado de la Investigación

1. Valor teórico: Extiende el alcance de la investigación del problema de posición general en la teoría de grafos tradicional, pasando de lo estático a lo dinámico
2. Aplicaciones prácticas: Proporciona fundamentos teóricos para la planificación de rutas y coordinación de robots móviles
3. Análisis de estructuras de grafos: Profundiza la comprensión de estructuras de grafos mediante el estudio del número de posición general en movimiento bajo diferentes operaciones de productos de grafos

Contribuciones Principales

1. Establecimiento de marco teórico fundamental: Proporciona cotas sistemáticas superiores e inferiores para el número de posición general en movimiento de productos cartesianos, coronas y grafos de unión
2. Cálculo de valores exactos: Proporciona fórmulas exactas para el número de posición general en movimiento de múltiples familias de grafos importantes, incluyendo:
   • Producto cartesiano de grafos completos: $\text{Mobgp}(K_n \square K_m)$
   • Grafos de malla: $\text{Mobgp}(P_n \square P_m) = 3$ (cuando $n,m \geq 3$)
   • Prismas de árboles: $\text{Mobgp}(T \square K_2) = \ell(T)$ (número de hojas)
   • Resultados parciales para grafos cilíndricos y toroidales
3. Análisis de la precisión de cotas: Demuestra la precisión de las cotas propuestas y proporciona familias de grafos específicas que alcanzan las cotas
4. Construcción algorítmica: Construye conjuntos específicos de posición general en movimiento y secuencias de movimiento para múltiples familias de grafos

Explicación Detallada de Métodos

Definición de Tareas

Conjunto de posición general: Un subconjunto de vértices $S$ de un grafo $G$ se denomina conjunto de posición general si ningún trío de vértices en $S$ se encuentra en el mismo camino más corto de $G$.

Conjunto de posición general en movimiento: Si comenzando desde un conjunto de posición general $S$, existe una serie de movimientos legales tal que cada vértice del grafo es visitado al menos una vez por algún robot, entonces $S$ se denomina conjunto de posición general en movimiento.

Movimiento legal: Un movimiento de un robot desde el vértice $u$ al vértice adyacente $v$, denotado $u \rightsquigarrow v$, es legal si y solo si:

1. $v$ no tiene actualmente un robot
2. La nueva configuración después del movimiento sigue siendo un conjunto de posición general

Número de posición general en movimiento: $\text{Mobgp}(G)$ denota el tamaño del conjunto máximo de posición general en movimiento del grafo $G$.

Métodos Técnicos Principales

1. Análisis de Cotas para Productos Cartesianos

Para el producto cartesiano $G \square H$, el artículo establece dos cotas inferiores importantes:

Proposición 2.1:

• $\text{Mobgp}(G \square H) \geq \max\{\text{Mobgp}(G), \text{Mobgp}(H)\}$
• $\text{Mobgp}(G \square H) \geq \max\{\text{gp}^o(G), \text{gp}^o(H)\}$

donde $\text{gp}^o(G)$ es el número de posición general exterior.

2. Técnica de Análisis de Capas

Utiliza la estructura de capas del producto cartesiano (capas $G$ y capas $H$) para el análisis:

• Capas $G$: Subgrafos inducidos por $V(G) \times \{h\}$, denotados como $G^h$
• Capas $H$: Subgrafos inducidos por $\{g\} \times V(H)$, denotados como ${}^gH$

3. Utilización de Convexidad

Observación clave: Las capas en el producto cartesiano son subgrafos convexos, lo que significa que los caminos más cortos dentro de una capa no abandonan esa capa.

4. Método de Prueba Constructiva

Para la prueba de cotas inferiores, el artículo utiliza el método constructivo:

1. Colocar robots en capas específicas
2. Diseñar secuencias de movimiento concretas
3. Verificar la legalidad de cada movimiento
4. Demostrar que todos los vértices pueden ser visitados

Puntos de Innovación Técnica

1. Estrategia de movimiento entre capas: Desarrolla técnicas para mover robots de forma segura entre diferentes capas, manteniendo la propiedad de posición general
2. Utilización de simetría: Aprovecha ingeniosamente la simetría del grafo para simplificar el diseño de secuencias de movimiento
3. Perspectivas de geometría combinatoria: Conecta el problema de posición general en movimiento con problemas de posición en geometría combinatoria
4. Construcción recursiva: Para ciertas familias de grafos, establece métodos de construcción recursivos

Configuración Experimental

Métodos de Verificación Teórica

Como artículo de matemática pura, este trabajo utiliza pruebas matemáticas rigurosas en lugar de verificación experimental:

1. Prueba constructiva: Demuestra cotas inferiores mediante construcción explícita de conjuntos de posición general en movimiento
2. Prueba por contradicción: Demuestra cotas superiores asumiendo la existencia de conjuntos más grandes y derivando una contradicción
3. Método de inducción: Utiliza inducción matemática para ciertas familias de grafos parametrizadas
4. Verificación asistida por computadora: Para casos complejos (como grafos toroidales), utiliza búsqueda computarizada para verificar resultados

Familias de Grafos Analizadas

1. Productos cartesianos de grafos completos: $K_r \square K_s$
2. Productos cartesianos de caminos: $P_n \square P_m$ (grafos de malla)
3. Prismas de árboles: $T \square K_2$
4. Grafos cilíndricos: $C_r \square P_s$
5. Grafos toroidales: $C_r \square C_s$
6. Coronas: $G \odot H$
7. Uniones: $G \vee H$

Resultados Experimentales

Resultados Teóricos Principales

1. Valores Exactos para Productos Cartesianos de Grafos Completos

Teorema 2.4: Para $n \geq m \geq 1$: