Caracterización de todos los grafos bien arista-dominados $K_4$-libres de cintura 3

Información Básica

• ID del Artículo: 2511.06095
• Título: Characterizing all $K_4$-free well-edge-dominated graphs of girth 3
• Autores: Sarah E. Anderson (University of St. Thomas), Kirsti Kuenzel (Trinity College)
• Clasificación: math.CO (Combinatoria)
• Fecha de Publicación: 11 de noviembre de 2025 (preimpresión)
• Enlace del Artículo: https://arxiv.org/abs/2511.06095

Resumen

Este artículo investiga el problema de dominación de aristas en teoría de grafos. Dado un grafo $G$, un conjunto de aristas $F$ se denomina conjunto arista-dominante si toda arista en $G$ está en $F$ o es adyacente a alguna arista en $F$. Un grafo $G$ se llama bien arista-dominado (well-edge-dominated) si todos sus conjuntos arista-dominantes minimales tienen la misma cardinalidad. Este artículo, basándose en trabajos previos, caracteriza completamente todos los grafos bien arista-dominados que contienen triángulos pero no contienen $K_4$ (grafo completo) como subgrafo inducido.

Antecedentes de Investigación y Motivación

Problema a Resolver

Este artículo tiene como objetivo caracterizar completamente los grafos que satisfacen las tres condiciones siguientes:

1. Bien arista-dominación (well-edge-dominated)
2. Cintura igual a 3 (es decir, contiene triángulos)
3. $K_4$-libre (no contiene $K_4$ como subgrafo inducido)

Importancia del Problema

1. Completitud Teórica: Los grafos bien arista-dominados están estrechamente relacionados con grafos equiemparejables (equimatchable graphs). Todo emparejamiento maximal es un conjunto arista-dominante minimal, por lo que los grafos bien arista-dominados son necesariamente equiemparejables. La caracterización completa de grafos bien arista-dominados es un objetivo importante en la teoría estructural de grafos.
2. Investigación Progresiva: Este problema forma parte de un plan de investigación sistemático:
   • 2010: Frendrup et al. demuestran que los grafos equiemparejables con cintura ≥5 son bien arista-dominados
   • 2022: Anderson et al. demuestran que los grafos bien arista-dominados no bipartitos con cintura ≥4 son solo 3 ($C_5, C_7, C_7^*$)
   • 2025: Berg et al. caracterizan los grafos bien arista-dominados con exactamente un triángulo
   • Este artículo: Caracteriza todos los grafos bien arista-dominados que contienen triángulos y son $K_4$-libres
3. Complejidad Computacional: Aunque existe un algoritmo de tiempo polinomial para reconocer grafos equiemparejables, la caracterización estructural sigue siendo un problema abierto, y este artículo proporciona un avance importante.

Limitaciones de Métodos Existentes

• El caso de cintura ≥4 ha sido prácticamente resuelto, pero el caso de cintura 3 (con triángulos) es mucho más complejo
• La caracterización existente del caso de un único triángulo no puede generalizarse directamente al caso de múltiples triángulos
• Se requieren nuevos métodos de construcción y técnicas de prueba para manejar las interacciones entre múltiples triángulos

Contribuciones Principales

1. Se definen tres clases de grafos infinitos:
   • Clase P (Grafos Hélice, Propellers): Formados por múltiples triángulos pegados en un vértice común
   • Clase W (Grafos Molino, Windmills): Formados por un grafo casa (house graph) y múltiples triángulos pegados en un vértice común
   • Clase G: La clase de construcción más general, formada pegando grafos bipartitos bien arista-dominados con componentes hélice, molino, rombo, etc., según reglas específicas
2. Teorema Principal (Teorema 4): Caracteriza completamente los grafos bien arista-dominados $K_4$-libres: $G \text{ es } K_4\text{-libre bien arista-dominado con cintura 3} \Leftrightarrow G \in \mathcal{G} \cup \{DH, F_5, Cr, W_1, W_2, W_3\}$ donde $DH$ (casa de ensueño), $Cr$ (grafo cristal), $F_5$ (abanico de 5 vértices), $W_1, W_2, W_3$ son cinco grafos excepcionales.
3. Se demuestra la bien arista-dominación de todos los grafos construidos:
   • Se prueba que todos los miembros de las clases P y W son bien arista-dominados (Lema 5)
   • Se prueba que todos los miembros de la clase G son bien arista-dominados (Corolario 1)
4. Prueba de Completitud: Mediante discusión exhaustiva de casos e inducción, se demuestra que todos los grafos bien arista-dominados $K_4$-libres están en la clasificación anterior.
5. Verificación Computacional: Se utiliza software Sage para verificar todos los grafos conexos bien arista-dominados de orden 7-8, proporcionando una base para la prueba teórica.

Explicación Detallada de Métodos

Definición de la Tarea

Entrada: Grafo $G = (V(G), E(G))$

Objetivo: Determinar si $G$ satisface:

1. Bien arista-dominación: $\gamma'(G) = \Gamma'(G)$ (todos los conjuntos arista-dominantes minimales tienen la misma cardinalidad)
2. Cintura igual a 3: Existe un ciclo de longitud 3 (triángulo)
3. $K_4$-libre: No contiene $K_4$ como subgrafo inducido

Salida: Si se satisface, determinar a qué clase de construcción pertenece $G$

Métodos de Construcción Principal

1. Definición de Clases de Grafos Base

Clase P (Hélice):

• Tomar $k$ triángulos disjuntos $T_1, \ldots, T_k$
• Seleccionar un vértice $v_i$ de cada $T_i$
• Pegar todos los $v_i$ en un único vértice (llamado "nariz")

Clase W (Molino):

• Basado en la clase P, agregar un grafo casa $H$
• El grafo casa contiene un triángulo y un 4-ciclo
• Pegar el vértice de grado 2 del triángulo del grafo casa con la nariz de la hélice

Clase G (Construcción General): Comenzar con los siguientes componentes:

• $G' = (A \cup B, E')$: Grafo bipartito conexo no trivial bien arista-dominado, con $|A| < |B|$
• $W_1, \ldots, W_k$: Molinos
• $P_1, \ldots, P_r$: Hélices
• $D_1, \ldots, D_\ell$: Rombos ($K_4 - e$)

Seleccionar $B' \subset B$ tal que $G' - B'$ sea bien arista-dominado y sin componentes triviales. Dividir $B' = \{s_1, \ldots, s_k, x_1, \ldots, x_r\}$ en:

• Vértices fuertemente separables $s_i$: Todos sus vecinos en $G' - B'$ son vértices de soporte
• Vértices separables $x_i$

Reglas de pegado:

• (a) La nariz de $W_i$ se pega con el vértice fuertemente separable $s_i$
• (b) La nariz de $P_i$ se pega con el vértice separable $x_i$
• (c) La nariz del rombo $D_i$ (vértice exterior) se pega con el vértice de soporte $y_i$ en $A$

2. Estrategia de Prueba de Bien Arista-Dominación

Lema 6 (Lema Clave): Si $G_1, G_2$ son grafos bien arista-dominados, $x \in V(G_1), y \in V(G_2)$ satisfacen:

• $G_1 - x$ es bien arista-dominado y $\gamma'(G_1 - x) = \gamma'(G_1)$
• $G_2 - y$ es bien arista-dominado y $\gamma'(G_2 - y) = \gamma'(G_2)$

Entonces el grafo $H$ obtenido pegando $x, y$ es bien arista-dominado, y $\gamma'(H) = \gamma'(G_1) + \gamma'(G_2)$

Esquema de Prueba: Para cualquier conjunto arista-dominante minimal $F$, se demuestra que $F \cap E(G_1 - x)$ y $F \cap E(G_2 - y)$ son conjuntos arista-dominantes minimales de los subgrafos correspondientes, por lo que sus cardinalidades son fijas.

Puntos de Innovación Técnica

1. Marco de Construcción Recursiva: Mediante la aplicación repetida del Lema 6, se descomponen grafos complejos en pegados de componentes simples
2. Concepto de Separabilidad: Se introduce la distinción entre separabilidad fuerte y ordinaria, caracterizando con precisión qué vértices pueden usarse para pegado
3. Estrategia de Discusión de Casos:
   • Inducción por el orden del grafo
   • Clasificación según si contiene rombo
   • Clasificación según la posición topológica de triángulos (hélice/molino/rombo)
   • Selección de aristas para contracción según la distancia del vértice a triángulos
4. Verificación Computacional con Sage: Se utiliza computadora para enumerar y verificar casos pequeños ($n \leq 8$), proporcionando base para inducción en casos grandes
5. Caracterización Estructural del Lema 7: Para estructuras topológicas especiales (conjunto independiente + triángulo + conjunto de conexión), se proporciona caracterización completa

Configuración Experimental

Método de Verificación Computacional

Herramienta: Software matemático Sage

Rango de Verificación:

• Todos los grafos conexos bien arista-dominados de orden 7 (Figuras 3 con $W_1$ a $W_{13}$)
• Todos los grafos conexos bien arista-dominados de orden 8 (Figuras 4 con $V_1$ a $V_{12}$)

Contenido de Verificación:

1. Enumerar todas las estructuras de grafos posibles
2. Verificar bien arista-dominación: calcular todos los conjuntos arista-dominantes minimales, verificar que tengan la misma cardinalidad
3. Verificar la propiedad $K_4$-libre
4. Clasificar en la clase de construcción correspondiente

Observación Clave (Observación 1)

Para grafos de orden 7 que contienen rombo: $G \text{ es } K_4\text{-libre bien arista-dominado} \Leftrightarrow G \in \{W_1, W_2, W_3, W_4\}$

Esto proporciona una base de clasificación importante para pruebas posteriores.

Resultados Experimentales

Enumeración Completa de Órdenes Pequeños

Grafos de Orden 7 (Figura 3):

• Total de 13 grafos conexos bien arista-dominados: $W_1$ a $W_{13}$
• Entre ellos, $W_1, W_2, W_3$ contienen rombo pero no están en la clase G (grafos excepcionales)
• $W_4$ contiene rombo pero está en la clase G (rombo con 3 aristas colgantes)
• $W_{10} \cong DH$ (casa de ensueño), $W_{12} \cong Cr$ (grafo cristal)
• Los demás están todos en $\mathcal{G}$

Grafos de Orden 8 (Figura 4):

• Total de 12 grafos conexos bien arista-dominados: $V_1$ a $V_{12}$
• Solo $V_1, V_2, V_3$ contienen rombo
• Todos los grafos están en $\mathcal{G} \cup \{W_1, W_2, W_3\}$

Verificación del Teorema Principal

Enunciado Completo del Teorema 4: Sea $G$ un grafo $K_4$-libre, entonces $G \text{ es bien arista-dominado con cintura 3} \Leftrightarrow G \in \mathcal{G} \cup \{DH, F_5, Cr, W_1, W_2, W_3\}$

Estructura de la Prueba:

1. Dirección Positiva (Corolario 1): Todos los grafos en $\mathcal{G}$ son bien arista-dominados
2. Dirección Negativa: Asumir la existencia de un contraejemplo minimal, derivar contradicción mediante:
   • Si contiene solo un triángulo, por Teorema 3 está en la clasificación
   • Si $n(G) \leq 8$, por verificación Sage está en la clasificación
   • Si $n(G) \geq 9$, seleccionar una arista apropiada $st$, considerar $G' = G - N_e[st]$
   • Para cada posibilidad de $G'$ (a qué clase pertenece), realizar discusión exhaustiva de casos
   • Cada caso implica $G \in \mathcal{G}$ o lleva a contradicción

Aplicación de Lemas Clave

Lema 7: Para grafos que satisfacen estructura topológica específica (conjunto independiente $I$, conjunto de conexión $S$, triángulo $xyz$), caracterización completa: $G \in \{Cr, H\} \cup \mathcal{K} \cup \mathcal{P} \cup \mathcal{R} \cup \mathcal{W}$

donde $\mathcal{K}$ (cometa), $\mathcal{R}$ son subclases de $\mathcal{G}$.

Método de Prueba:

• Seleccionar contraejemplo minimal
• Discusión de casos según si $I$ es vacío
• Discusión de casos según si $S$ es independiente
• Mediante eliminación de aristas, inducción y razonamiento por contradicción

Trabajos Relacionados

Investigación de Grafos Equiemparejables

1. Trabajos Tempranos:
   • Lewin (1974), Meng (1974): Definen independientemente grafos equiemparejables
   • Lesk, Plummer, Pulleyblank (1984): Algoritmo de reconocimiento en tiempo polinomial
2. Caracterización Estructural:
   • Sumner (1979, Teorema 1): Grafos aleatoriamente emparejables son solo $K_{2n}$ o $K_{n,n}$
   • Frendrup et al. (2010): Caracterización de grafos equiemparejables con cintura ≥5
   • Büyükçolak et al. (2022): Grafos equiemparejables no bipartitos con 4-ciclo
3. Grafos Bipartitos Equiemparejables:
   • Lema 1 (Propiedad Clave): Si $G = (A \cup B, E)$ es equiemparejable con $|A| < |B|$, entonces cada vértice en $A$ es vértice de soporte o está en $K_{2,2}$

Investigación de Grafos Bien Arista-Dominados

1. Caso de Cintura ≥4:
   • Teorema 2 (Anderson et al., 2022): Los grafos bien arista-dominados con cintura ≥4 son bipartitos o uno de $\{C_5, C_7, C_7^*\}$
2. Caso de Un Único Triángulo:
   • Teorema 3 (Berg et al., 2025): Caracterización completa de grafos bien arista-dominados con exactamente un triángulo como $\mathcal{T} \cup \mathcal{F} \cup \{K_3, Cr, H, DH\}$
3. Contribución de Este Artículo: Completa el caso de cintura 3 y $K_4$-libre, avanzando significativamente hacia caracterización completa

Herramientas Técnicas

• Lema 3 (Anderson et al., 2022): Si $M$ es emparejamiento y $G$ es bien arista-dominado, entonces $G - N_e[M]$ es bien arista-dominado
• Lema 4: Si $y \in A$ no es vértice de soporte, existe conjunto arista-dominante minimal que no contiene aristas incidentes a $y$

Conclusiones y Discusión

Conclusiones Principales

1. Clasificación Completa: Todos los grafos bien arista-dominados $K_4$-libres con cintura 3 pertenecen a:
   • Clase infinita $\mathcal{G}$ (que contiene subclases $\mathcal{P}, \mathcal{W}, \mathcal{K}, \mathcal{R}$)
   • Cinco excepciones finitas: $DH, F_5, Cr, W_1, W_2, W_3$
2. Método de Construcción: Se proporciona marco sistemático de construcción, comenzando desde grafos bipartitos bien arista-dominados, generando todos los grafos posibles mediante operaciones de pegado
3. Suficiencia y Necesidad: Se demuestra tanto que todos los grafos construidos son bien arista-dominados (suficiencia) como que todos los grafos que satisfacen las condiciones están en la construcción (necesidad)

Limitaciones

1. Dependencia de Grafos Bipartitos: La construcción depende de grafos bipartitos bien arista-dominados, pero estos aún carecen de caracterización estructural completa (sigue siendo problema abierto)
2. Restricción $K_4$: Este artículo solo trata el caso $K_4$-libre; los grafos bien arista-dominados que contienen $K_4$ aún no se han resuelto
3. Rango de Verificación Computacional: Solo se verifica hasta orden 8; órdenes mayores dependen de la corrección de la prueba teórica
4. Esencia de Grafos Excepcionales: Por qué los 5 grafos excepcionales no pueden incorporarse en marco unificado carece de explicación profunda

Direcciones Futuras

La Sección 3 especifica explícitamente:

"el paso final para caracterizar todos los grafos no bipartitos bien arista-dominados sería caracterizar aquellos que contienen un $K_4$ inducido."

Direcciones específicas:

1. Caso que Contiene $K_4$: Los autores creen que puede caracterizarse agregando $K_4$ a grafos en $\mathcal{G}$
2. Grafos Bipartitos Bien Arista-Dominados: Caracterización completa de la estructura de grafos bipartitos bien arista-dominados
3. Implementación de Algoritmos: Basado en resultados de caracterización, diseñar algoritmos de reconocimiento más eficientes
4. Generalización: Investigar propiedades de dominación de aristas más generales, como dominación de $k$-aristas

Evaluación Profunda

Fortalezas

1. Completitud Teórica:
   • Resuelve completamente el caso $K_4$-libre con cintura 3, llenando vacío importante
   • Prueba rigurosa, discusión exhaustiva de casos (Casos 1-3, cada uno con múltiples subcasos anidados)
   • Argumentación completa en ambas direcciones
2. Innovación de Métodos:
   • Introduce concepto de separabilidad fuerte, caracterizando con precisión condiciones de pegado
   • Lema 6 proporciona marco modular para construcción y prueba
   • Combina verificación computacional y prueba teórica, apoyándose mutuamente
3. Claridad Estructural:
   • De simple a complejo: $\mathcal{P} \subset \mathcal{W} \subset \mathcal{G}$
   • Reglas de construcción explícitas, fáciles de verificar y aplicar
   • Apéndice lista detalladamente definiciones de todas las clases
4. Apoyo de Visualización:
   • Figuras 1-4 proporcionan representación intuitiva de grafos clave
   • Enumeración completa de todos los grafos de orden 7-8 aumenta credibilidad

Insuficiencias

1. Complejidad de Prueba:
   • La prueba del Teorema 4 se extiende por 12 páginas (páginas 12-24), con discusión de casos extremadamente tediosa
   • Ciertos argumentos dependen de muchos lemas preliminares, difícil de rastrear
   • Legibilidad afectada, difícil captar rápidamente ideas centrales
2. Tratamiento de Grafos Excepcionales:
   • La aparición de 5 grafos excepcionales parece abrupta, carece de explicación unificada
   • ¿Por qué $W_1, W_2, W_3$ no pueden incorporarse en $\mathcal{G}$? Las razones teóricas no son suficientemente claras
3. Caja Negra de Grafos Bipartitos:
   • La construcción depende fuertemente de grafos bipartitos bien arista-dominados, pero su estructura es desconocida
   • Esto hace que la construcción no sea suficientemente "explícita", limitando aplicaciones
4. Detalles Computacionales Faltantes:
   • El código Sage específico de verificación y algoritmos no se proporcionan
   • No se puede reproducir independientemente resultados computacionales
   • Complejidad computacional no analizada
5. Discusión Insuficiente de Generalización:
   • ¿Pueden los métodos generalizarse al caso que contiene $K_4$?
   • ¿Relaciones con otras clases de grafos (como grafos planares, grafos sin garras)?

Influencia

1. Contribución Teórica:
   • Sienta base para caracterización completa de grafos no bipartitos bien arista-dominados
   • El marco de construcción proporcionado puede aplicarse a caracterización de otras clases de grafos
   • Avanza desarrollo de teoría estructural de grafos equiemparejables
2. Valor Metodológico:
   • Paradigma de combinación de verificación computacional + prueba teórica
   • Ideas de construcción modular y operaciones de pegado
   • El concepto de separabilidad puede tener aplicaciones más amplias
3. Practicidad Limitada:
   • Principalmente resultado teórico puro, escenarios de aplicación directa limitados
   • Algoritmo de reconocimiento no mejorado (ya existe algoritmo polinomial)
   • Significado orientador para diseño de algoritmos aún por explorar
4. Reproducibilidad:
   • Prueba teórica verificable (aunque tediosa)
   • Parte computacional tiene pobre reproducibilidad (código no publicado)
   • Definiciones de construcción claras, fáciles de implementar

Escenarios Aplicables

1. Investigación Teórica:
   • Investigadores en teoría de estructura de grafos
   • Investigación en teoría de grafos equiemparejables y dominación
   • Combinatoria extremal
2. Diseño de Algoritmos:
   • Puede inspirar algoritmos eficientes en clases especiales de grafos
   • Diseño de algoritmos parametrizados (con número de triángulos como parámetro)
3. Problemas Relacionados:
   • Problemas de cobertura de aristas, coloración de aristas
   • Problemas relacionados con emparejamientos perfectos
   • Otras variantes de dominación

Referencias

Citas Clave:

2 Anderson et al. (2022): Caracterización de grafos bien arista-dominados con cintura ≥4 (base del Teorema 2)

3 Berg et al. (2025): Caracterización de grafos bien arista-dominados con un único triángulo (base del Teorema 3)

5 Büyükçolak et al. (2023): Propiedades de grafos bipartitos equiemparejables (Lema 1)

9 Frendrup et al. (2010): Grafos equiemparejables con cintura ≥5

11 Lesk et al. (1984): Algoritmo de reconocimiento polinomial para grafos equiemparejables

14 Sumner (1979): Caracterización de grafos aleatoriamente emparejables (Teorema 1)

Evaluación General: Este es un artículo de alta calidad en matemática combinatoria teórica que, mediante discusión rigurosa de casos y prueba constructiva, resuelve completamente el problema de caracterización de grafos bien arista-dominados $K_4$-libres. Aunque la prueba es tediosa y depende de problemas bipartitos no resueltos, tiene contribuciones significativas en completitud teórica e innovación metodológica. Es un avance sólido en el campo para promover la caracterización completa de grafos bien arista-dominados y equiemparejables.