Gráfico cuyo hipergráfico 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 sólo si el hipergrafo de sus camarillas máximas es el dual de un hiperárbol. Originalmente, estos gráficos se definieron mediante ordenamientos máximos de vecindad y tienen una variedad de caracterizaciones diferentes. [1] A diferencia de los gráficos dualmente cordales, la propiedad de ser dualmente cordal no es hereditaria, es decir, los subgrafos inducidos de un gráfico dualmente cordal no son necesariamente dualmente cordales (los gráficos hereditariamente dualmente cordales son exactamente los gráficos fuertemente cordales ), y un gráfico dualmente cordal En general no es un gráfico perfecto .
Los gráficos dualmente cordales aparecieron por primera vez con el nombre de HT-graphs . [2]
Caracterizaciones
Los gráficos dualmente cordales son los gráficos de camarillas de gráficos cordales , [3] es decir, los gráficos de intersección de camarillas máximas de gráficos cordales.
Las siguientes propiedades son equivalentes: [4]
- G tiene un ordenamiento de vecindad máximo.
- Hay 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 hipergráfico 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 sólo si su cuadrado es cordal y su hipergrafo de vecindad cerrada tiene la propiedad de Helly .
En De Caria y Gutiérrez (2012) los grafos dualmente cordales se caracterizan en términos de propiedades separadoras. En Brešar (2003) se demostró que las gráficas dualmente cordales son precisamente las gráficas de intersección de hipercubos máximos de gráficas de complejos cúbicos acíclicos.
La estructura y el uso algorítmico de grafos doblemente cordales viene dado por Moscarini (1993). Estos son gráficos que son cordales y dualmente cordales.
Reconocimiento
Los gráficos dualmente cordales se pueden reconocer en tiempo lineal, y se puede encontrar un orden 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 grafos dualmente cordales, algunas variantes del problema del conjunto mínimo dominante y el árbol de Steiner se pueden resolver eficientemente en grafos dualmente cordales (pero la dominación independiente sigue siendo NP -completo ). [6] Véase Brandstädt, Chepoi y Dragan (1999) para el uso de propiedades de gráficos dualmente cordales para llaves de árboles, y consulte Brandstädt, Leitert y Rautenbach (2012) para un algoritmo de tiempo lineal de dominación eficiente y dominación eficiente de bordes en gráficos duales 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, Víctor; Dragan, Feodor (1998), "El uso algorítmico de la estructura de hiperárbol y los ordenamientos máximos de vecindad", Matemáticas Aplicadas Discretas , 82 (1–3): 43–77, doi : 10.1016/s0166-218x(97)00125-x.
- Brandstädt, Andreas; Chepoi, Víctor; Dragan, Feodor (1999), "Distancia que aproxima árboles para gráficos cordales y dualmente cordales", Journal of Algorithms , 30 : 166–184, doi :10.1006/jagm.1998.0962.
- Brandstädt, Andreas; Dragan, Feodor; Chepoi, Víctor; Voloshin, Vitaly (1998), "Gráficos dualmente cordales", Revista SIAM de Matemáticas Discretas , 11 (3): 437–455, doi :10.1137/S0895480193253415, MR 1628114.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Clases de gráficos: una encuesta , Monografías de SIAM sobre aplicaciones y matemáticas discretas, ISBN 0-89871-432-X.
- Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Conjuntos eficientes dominantes y dominantes de bordes para gráficos e hipergráficos", en Chao, Kun-Mao; Hsu, Tsan-sheng; Lee, Der-Tsai (eds.), Algoritmos y Computación - 23º Simposio Internacional, ISAAC 2012, Taipei, Taiwán, 19 al 21 de diciembre de 2012. Actas , Lecture Notes in Computer Science , vol. 7676, Springer, págs. 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 Caría, Pablo; Gutiérrez, Marisa (2012), "Sobre separadores de vértices mínimos de gráficos dualmente cordales: propiedades y caracterizaciones", Matemáticas aplicadas discretas , 160 (18): 2627–2635, doi : 10.1016/j.dam.2012.02.022 , hdl : 11336 /190841.
- Dragan, Feodor (1989), Centros de gráficos y propiedad de Helly (en ruso) , Ph.D. tesis, Universidad Estatal de Moldavia, Moldavia.
- Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Problemas de ubicación en gráficos y la propiedad de Helly (en ruso)", Matemáticas discretas. (Moscú) , 4 : 67–73.
- Dragan, Feodor (1993), "Grafos HT: centros, dominación r conectada y árboles de Steiner", Comput. Ciencia. J. de Moldavia (Kishinev) , 1 : 64–83.
- Gutiérrez, Marisa; Oubina, L. (1996), "Caracterizaciones métricas de gráficos de intervalos adecuados y gráficos de camarilla de árbol", 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 de SIAM sobre aplicaciones y matemáticas discretas.
- 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), "Clique Graphs of Chordal and Path Graphs", Revista SIAM de Matemáticas Discretas , 7 (2): 331–336, CiteSeerX 10.1.1.52.521 , doi :10.1137/s0895480191223191.
