stringtranslate.com

Gráfica dualmente cordal

En el área matemática de la teoría de grafos , un grafo no dirigido G es dualmente cordal si el hipergrafo de sus camarillas máximas es un hiperárbol . El nombre proviene del hecho de que un grafo es cordal si y solo si el hipergrafo de sus camarillas máximas es el dual de un hiperárbol. Originalmente, estos grafos se definían por ordenamientos de vecindad máxima y tienen una variedad de caracterizaciones diferentes. [1] A diferencia de los grafos cordales, la propiedad de ser dualmente cordal no es hereditaria, es decir, los subgrafos inducidos de un grafo dualmente cordal no son necesariamente dualmente cordales (los grafos dualmente cordales hereditariamente son exactamente los grafos fuertemente cordales ), y un grafo dualmente cordal en general no es un grafo perfecto .

Los grafos dualmente cordales aparecieron por primera vez bajo el nombre de grafos HT . [2]

Caracterizaciones

Los grafos dualmente cordales son los grafos de camarilla de grafos cordales , [3] es decir, los grafos de intersección de camarillas máximas de grafos cordales.

Las siguientes propiedades son equivalentes: [4]

La condición del hipergrafo de vecindad cerrada también implica que un grafo es dualmente cordal si y solo si su cuadrado es cordal y su hipergrafo de vecindad cerrada tiene la propiedad de Helly .

En De Caria y Gutiérrez (2012) se caracterizan los grafos dualmente cordales en términos de propiedades separadoras. En Brešar (2003) se demostró que los grafos dualmente cordales son precisamente los grafos de intersección de hipercubos máximos de grafos de complejos cúbicos acíclicos.

La estructura y el uso algorítmico de los grafos doblemente cordales está dada por Moscarini (1993). Se trata de grafos que son cordales y dualmente cordales.

Reconocimiento

Los gráficos dualmente cordales se pueden reconocer en tiempo lineal, y se puede encontrar un ordenamiento de vecindad máximo de un gráfico dualmente cordal en tiempo lineal. [5]

Complejidad de los problemas

Si bien algunos problemas básicos como el conjunto independiente máximo , la camarilla máxima , la coloración y la cobertura de camarilla siguen siendo NP-completos para los grafos dualmente cordales, algunas variantes del problema del conjunto mínimo dominante y el árbol de Steiner se pueden resolver de manera eficiente en grafos dualmente cordales (pero la dominación independiente sigue siendo NP-completa ). [6] Véase Brandstädt, Chepoi y Dragan (1999) para el uso de propiedades de grafos dualmente cordales para generadores de árboles, y véase Brandstädt, Leitert y Rautenbach (2012) para un algoritmo de tiempo lineal de dominación eficiente y dominación de aristas eficiente en grafos dualmente cordales.

Notas

  1. ^ Brandstädt y col. (1998); Brandstädt, Le y Spinrad (1999)
  2. ^ Dragan (1989); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)
  3. ^ Gutiérrez y Oubina (1996); Szwarcfiter y Bornstein (1994)
  4. ^ Brandstädt, Chepoi y Dragan (1998);Brandstädt et al. (1998); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)
  5. ^ Brandstädt, Chepoi y Dragan (1998);Dragan (1989)
  6. ^ Brandstädt, Chepoi y Dragan (1998); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)

Referencias