2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

Coloración de visibilidad mutua a distancia: relaciones con (total) dominación, grafos de distancia exacta y productos de grafos

Información Básica

  • ID del Artículo: 2510.10284
  • Título: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • Autores: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • Clasificación: math.CO (Matemática Combinatoria)
  • Fecha de Publicación: 11 de octubre de 2025
  • Enlace del Artículo: https://arxiv.org/abs/2510.10284

Resumen

Este artículo estudia el problema de coloración de visibilidad mutua a distancia k, que es una extensión del concepto de visibilidad mutua introducido por Di Stefano en 2022. Para un subconjunto S de vértices del grafo G, se dice que S es un conjunto de visibilidad mutua a distancia k (conjunto k-DMV) si para cualesquiera dos vértices en S existe una geodésica de longitud a lo sumo k cuyos vértices internos no pertenecen a S. El artículo combina este concepto con la coloración de visibilidad mutua, definiendo el número cromático de visibilidad mutua a distancia k, χ_μ_k(G). Los resultados más interesantes se producen cuando k=2, demostrando que χ_μ_2(G) ≤ |V(G)|/2 y estableciendo conexiones profundas con el número de dominación, el número de dominación total y los grafos de distancia exacta.

Antecedentes y Motivación de la Investigación

  1. Origen del Problema: El concepto de visibilidad mutua fue propuesto originalmente por Di Stefano en 2022, relacionándose con el problema clásico de "tres puntos no colineales" y con problemas de reposicionamiento de robots móviles en planos.
  2. Motivación de la Investigación:
    • Aunque el concepto de visibilidad mutua es novedoso, ha recibido amplia atención (más de 20 citas en MathSciNet)
    • La investigación existente se enfoca principalmente en la cardinalidad máxima de conjuntos de visibilidad mutua, careciendo de un estudio sistemático de problemas de coloración
    • La restricción de distancia k hace que la comunicación sea más eficiente, con valor de aplicación práctica
  3. Significado Práctico: En redes de computadoras o redes sociales, los vértices con propiedades de visibilidad mutua pueden representar entidades que requieren comunicación eficiente y confidencial, asegurando que los mensajes no se transmitan a través de otras entidades.

Contribuciones Principales

  1. Introducción de Nuevo Concepto: Define por primera vez el número cromático de visibilidad mutua a distancia k, χ_μ_k(G), unificando el número de cobertura de cliques (k=1) y el número cromático de visibilidad mutua (k≥diam(G))
  2. Establecimiento de Límites Fundamentales:
    • Demuestra que χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ y proporciona familias de grafos que alcanzan este límite
    • Para grafos sin vértices aislados, χ_μ_2(G) ≤ γ_t(G)
    • Para grafos con cintura al menos 7, χ_μ_2(G) ≥ γ(G)
  3. Descubrimiento de Conexiones con Grafos de Distancia Exacta: Demuestra que para grafos sin vértices aislados y cintura al menos 7, θ(G♮2) = γ_t(G)
  4. Estudio Sistemático de Productos de Grafos:
    • Producto lexicográfico: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • Producto fuerte: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • Producto cartesiano: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. Caracterización de Clases de Grafos Especiales: Caracteriza completamente los grafos de bloques que satisfacen χ_μ_k(G) = χ_μ(G) donde k = diam(G)-1

Explicación Detallada de Métodos

Definición de la Tarea

Dado un grafo G y un entero positivo k, una coloración de visibilidad mutua a distancia k es una partición de V(G) en varios conjuntos k-DMV. Un conjunto k-DMV M satisface: para cualesquiera dos vértices u,v en M, existe una geodésica u,v de longitud a lo sumo k cuyos vértices internos no pertenecen a M.

Entrada: Grafo G = (V,E), entero positivo k Salida: Una partición {S_1, S_2, ..., S_t} de V(G) tal que cada S_i es un conjunto k-DMV Objetivo: Minimizar el número de conjuntos en la partición t

Métodos Técnicos Principales

1. Establecimiento de Teoría Fundamental

Observación 1: Para un grafo G con diámetro d, existe una cadena de monotonía: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

Observación 2: Límite inferior fundamental χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. Análisis Profundo del Caso k=2

Teorema 4: Para cualquier grafo conexo G, χ_μ_2(G) ≤ ⌈n/2⌉

Esquema de Prueba: Mediante construcción inductiva sobre árboles generadores, descomponiendo el árbol en estructuras que pueden colorearse con dos colores.

Teorema 5: Si G no tiene vértices aislados, entonces χ_μ_2(G) ≤ γ_t(G)

Método de Prueba: Prueba constructiva utilizando un conjunto de dominación total D = {v_1,...,v_γ_t(G)}, definiendo D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j), demostrando que cada D_i es un conjunto 2-DMV.

3. Relación entre Cintura y Número de Dominación

Lema 6: Si g(G) ≥ 7, entonces cada clase de color C en una coloración χ_μ_2(G) es un subconjunto de la vecindad cerrada de algún vértice.

Teorema 7: Si g(G) ≥ 7, entonces χ_μ_2(G) ≥ γ(G)

Puntos de Innovación Técnica

  1. Marco Unificado: Unifica la cobertura de cliques y la coloración de visibilidad mutua en el marco de coloración k-DMV
  2. Caracterización Precisa de Condiciones de Cintura: Demuestra que la cintura 7 es el valor mínimo que garantiza χ_μ_2(G) ≥ γ(G)
  3. Conexión con Grafos de Distancia Exacta: Establece por primera vez una conexión profunda entre coloración 2-DMV y grafos de distancia exacta-2
  4. Análisis Sistemático de Productos de Grafos: Proporciona límites ajustados para tres productos de grafos principales

Configuración Experimental

Métodos de Verificación Teórica

El artículo utiliza principalmente métodos de prueba teórica, verificando la precisión de los límites mediante la construcción de familias de grafos específicas:

  1. Caminos y Ciclos: Calcula los valores exactos de χ_μ_k para P_n y C_n
  2. Familias de Grafos Especiales: Construye familias de grafos que alcanzan varios límites
  3. Grafos Producto: Analiza las propiedades de productos de grafos específicos como P_n⊠K_m

Análisis de Instancias Clave

Proposición 2:

  • Para el camino P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • Para el ciclo C_n: χ_μ_k(C_n) = ⌈n/3⌉ (cuando n ≤ 3k), ⌈n/2⌉ (en caso contrario)

Proposición 12: Para P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + término_de_corrección

Resultados Experimentales

Resultados Teóricos Principales

  1. Precisión de Límites Fundamentales:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ es válido para todos los grafos, siendo alcanzado por caminos y ciclos largos
    • χ_μ_2(G) ≤ γ_t(G) es válido para grafos sin vértices aislados, pudiendo construirse familias de grafos donde la diferencia es arbitrariamente grande
  2. Optimalidad de Condiciones de Cintura:
    • Se construye un contraejemplo con cintura 6 donde γ(G) = 5 > χ_μ_2(G) = 3
    • Se demuestra que la cintura 7 es la condición mínima que garantiza χ_μ_2(G) ≥ γ(G)
  3. Precisión de Resultados de Productos de Grafos:
    • El límite de producto fuerte χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) es alcanzado por familias infinitas de grafos
    • El límite inferior del producto cartesiano es alcanzado por grafos toroidales

Conexión Sorprendente con Grafos de Distancia Exacta

Teorema 8: Si G no tiene vértices aislados y g(G) ≥ 7, entonces θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

Este resultado establece una relación de igualdad entre tres parámetros de grafos aparentemente no relacionados, con importante significado teórico.

Propiedades Especiales de Hipercubos

Proposición 16: Para el hipercubo n-dimensional Q_n, χ_μ_2(Q_n) ≤ γ(Q_n)

Conjetura: χ_μ_2(Q_n) = γ(Q_n) para todo n

Trabajo Relacionado

  1. Investigación de Visibilidad Mutua: Di Stefano (2022) introduce el concepto fundamental, Cera et al. lo extienden a la versión de distancia k
  2. Coloración de Visibilidad Mutua: Klavžar et al. (2025) estudian por primera vez el problema de coloración de visibilidad mutua
  3. Grafos de Distancia Exacta: Introducidos en los años 1980, recientemente han recibido renovada atención
  4. Teoría de Dominación: Campo clásico de investigación en teoría de grafos, estableciendo nuevas conexiones con este artículo

Conclusiones y Discusión

Conclusiones Principales

  1. La coloración de visibilidad mutua a distancia k proporciona una nueva perspectiva para estudiar propiedades estructurales de grafos
  2. El caso k=2 revela conexiones profundas con teoría de dominación y grafos de distancia exacta
  3. El comportamiento bajo diferentes productos de grafos revela características esenciales de este parámetro
  4. Las condiciones de cintura juegan un papel clave en la determinación de límites de parámetros

Limitaciones

  1. Los resultados principales se concentran en el caso k=2, con investigación limitada para valores generales de k
  2. La precisión de ciertos límites se verifica solo en familias de grafos específicas
  3. No se abordan cuestiones de complejidad computacional

Direcciones Futuras

El artículo propone tres problemas abiertos específicos:

Problema 1: Caracterizar grafos de bloques G que satisfacen χ_μ_2(G) = θ(G)

Problema 2: Para grafos conexos G,H, ¿se cumple χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}?

Problema 3: ¿Se cumple χ_μ_2(Q_n) = γ(Q_n) para todos los hipercubos?

Evaluación Profunda

Fortalezas

  1. Profundidad Teórica: Establece nuevas conexiones entre múltiples ramas de la teoría de grafos, particularmente con teoría de dominación y grafos de distancia exacta
  2. Completitud de Resultados: Proporciona numerosos límites ajustados y construye familias de grafos que alcanzan estos límites
  3. Innovación Técnica: La caracterización precisa de condiciones de cintura y el análisis sistemático de productos de grafos demuestran técnicas sofisticadas
  4. Claridad de Escritura: Definiciones claras, pruebas rigurosas y estructura lógica

Deficiencias

  1. Ausencia de Complejidad Computacional: No se discute la complejidad computacional de χ_μ_k(G)
  2. Limitaciones de Aplicación: Aunque se mencionan aplicaciones en comunicaciones de red, falta análisis de escenarios de aplicación concretos
  3. Falta de Diseño de Algoritmos: Carece de algoritmos eficientes para calcular o aproximar χ_μ_k(G)

Impacto

  1. Contribución Teórica: Abre nuevas direcciones para investigación en teoría de grafos, esperándose investigaciones posteriores
  2. Valor Técnico: Las técnicas de prueba y métodos de construcción tienen valor de referencia para investigación relacionada
  3. Potencial Interdisciplinario: Las conexiones con teoría de dominación pueden promover desarrollo de colaboración entre campos

Escenarios de Aplicación

  1. Diseño de Redes: Aplicación en redes que requieren garantizar privacidad de rutas de comunicación
  2. Investigación en Teoría de Grafos: Como nueva herramienta para estudiar propiedades estructurales de grafos
  3. Optimización Combinatoria: Proporciona fundamentos teóricos para problemas de optimización relacionados

Referencias Bibliográficas

El artículo cita 18 referencias relacionadas, incluyendo principalmente:

  • Di Stefano (2022): Literatura original del concepto de visibilidad mutua
  • Cera et al.: Extensión de visibilidad mutua a distancia k
  • Klavžar et al.: Primera investigación de coloración de visibilidad mutua
  • Libros de texto clásicos de teoría de grafos y literatura de teoría de dominación

Evaluación General: Este es un artículo de alta calidad en teoría de grafos teórica que realiza contribuciones importantes en la dirección de investigación emergente de visibilidad mutua. El artículo no solo establece un marco teórico completo, sino que también descubre conexiones profundas con conceptos clásicos de teoría de grafos, sentando una base sólida para el desarrollo de este campo. Aunque aún hay investigación pendiente en aspectos de aplicación y algoritmos, su valor teórico e innovación lo convierten en literatura importante en este campo.