Gráfico cuyo hipergrafo de camarilla máxima es un hiperárbol
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]
- G tiene un ordenamiento de vecindad máximo.
- Existe un árbol de expansión T de G tal que cualquier camarilla máxima de G induce un subárbol en T.
- El hipergrafo de vecindad cerrada N(G) de G es un hiperárbol .
- El hipergrafo de camarilla máxima de G es un hiperárbol .
- G es el gráfico de 2 secciones de un hiperárbol .
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
- ^ Brandstädt y col. (1998); Brandstädt, Le y Spinrad (1999)
- ^ Dragan (1989); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)
- ^ Gutiérrez y Oubina (1996); Szwarcfiter y Bornstein (1994)
- ^ Brandstädt, Chepoi y Dragan (1998);Brandstädt et al. (1998); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)
- ^ Brandstädt, Chepoi y Dragan (1998);Dragan (1989)
- ^ Brandstädt, Chepoi y Dragan (1998); Dragan, Prisacaru y Chepoi (1992); Dragán (1993)
Referencias
- Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), "El uso algorítmico de la estructura de hiperárbol y los ordenamientos de vecindad máxima", Discrete Applied Mathematics , 82 (1–3): 43–77, doi : 10.1016/s0166-218x(97)00125-x.
- Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), "Árboles de aproximación de distancias para grafos cordales y dualmente cordales", Journal of Algorithms , 30 : 166–184, doi :10.1006/jagm.1998.0962.
- Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Gráficos dualmente cordales", SIAM Journal on Discrete Mathematics , 11 (3): 437–455, doi :10.1137/S0895480193253415, MR 1628114.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Clases de grafos: un estudio , Monografías SIAM sobre matemáticas discretas y aplicaciones, ISBN 0-89871-432-X.
- Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Conjuntos dominantes y dominantes de aristas eficientes para grafos e hipergrafos", en Chao, Kun-Mao; Hsu, Tsan-sheng; Lee, Der-Tsai (eds.), Algorithms and Computation – 23rd International Symposium, ISAAC 2012, Taipei, Taiwán, 19-21 de diciembre de 2012. Proceedings , Lecture Notes in Computer Science , vol. 7676, Springer, pp. 267-277, arXiv : 1207.0953 , doi :10.1007/978-3-642-35261-4_30.
- Brešar, Boštjan (2003), "Gráficos de intersección de hipercubos máximos", European Journal of Combinatorics , 24 (2): 195–209, doi : 10.1016/s0195-6698(02)00142-7.
- De Caria, Pablo; Gutierrez, Marisa (2012), "Sobre separadores de vértices mínimos de grafos dualmente cordales: propiedades y caracterizaciones", Discrete Applied Mathematics , 160 (18): 2627–2635, doi : 10.1016/j.dam.2012.02.022 , hdl : 11336/190841.
- Dragan, Feodor (1989), Centros de grafos y la propiedad de Helly (en ruso) , tesis doctoral, Universidad Estatal de Moldavia, Moldavia.
- Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Problemas de localización en grafos y la propiedad de Helly (en ruso)", Discrete Math. (Moscú) , 4 : 67–73.
- Dragan, Feodor (1993), "Grafos HT: centros, dominación r conectada y árboles de Steiner", Comput. Sci. J. of Moldova (Kishinev) , 1 : 64–83.
- Gutierrez, Marisa; Oubina, L. (1996), "Caracterizaciones métricas de gráficos de intervalos propios y gráficos de árbol-camarilla", Journal of Graph Theory , 21 (2): 199–205, doi :10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m.
- McKee, Terry A.; McMorris, FR. (1999), Temas de teoría de grafos de intersección , Monografías SIAM sobre matemáticas discretas y aplicaciones.
- Moscarini, Marina (1993), "Gráficos doblemente cordales, árboles de Steiner y dominación conectada", Networks , 23 : 59–69, doi :10.1002/net.3230230108.
- Szwarcfiter, Jayme L.; Bornstein, Claudson F. (1994), "Gráficos de camarilla de gráficos de cuerdas y de trayectorias", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, CiteSeerX 10.1.1.52.521 , doi :10.1137/s0895480191223191.