En el área matemática de la teoría de grafos , un grafo no dirigido G es doblemente cordal si el hipergrafo de sus camarillas máximas es un hipertá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 hipertárbol. Originalmente, estos gráficos se definían por orden 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 (hereditariamente los grafos dualmente cordales son exactamente losgrafos fuertemente cordales ), y un grafo dualmente cordal no es en general un grafo perfecto . Los gráficos dualmente cordales aparecieron primero bajo el nombre de gráficos HT . [2]
Caracterizaciones
Las gráficas doblemente cordales son las gráficas de pandillas de las gráficas de cuerdas , [3] es decir, las gráficas de intersección de las pandillas máximas de las gráficas de cuerdas.
Las siguientes propiedades son equivalentes: [4]
- G tiene un orden 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 de T .
- El hipergrafo de vecindad cerrada N (G) de G es un hipertárbol .
- El hipergráfico de la camarilla máxima de G es un hipertárbol .
- G es el gráfico de dos secciones de un árbol hipertrófico .
La condición en el hipergráfico de vecindad cerrada también implica que un gráfico es doblemente cordal si y solo si su cuadrado es cordal y su hipergrama de vecindad cerrada tiene la propiedad de Helly .
En De Caria & Gutierrez (2012) los grafos dualmente cordales se caracterizan en términos de propiedades de separador. En Brešar (2003) se demostró que los gráficos dualmente cordales son precisamente los gráficos de intersección de hipercubos máximos de gráficos de complejos cúbicos acíclicos.
Moscarini (1993) da la estructura y el uso algorítmico de grafos doblemente cordales . Estos son gráficos que son acordes 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 problemas
Si bien algunos problemas básicos, como el conjunto máximo independiente , la camarilla máxima , el color y la cobertura de la camarilla siguen siendo NP-completos para gráficos dualmente cordales, algunas variantes del problema del conjunto mínimo dominante y el árbol de Steiner se pueden resolver de manera eficiente en gráficos dualmente cordales (pero la Dominación independiente sigue siendo NP -completo ). [6] Ver Brandstädt, Chepoi & Dragan (1999) para el uso de propiedades de grafos dualmente cordales para las llaves de árbol, y ver Brandstädt, Leitert y Rautenbach (2012) para un algoritmo de tiempo lineal de dominación eficiente y dominación de bordes eficiente en grafos dualmente cordales. .
Notas
- ^ Brandstädt y col. (1993) ; Brandstädt, Chepoi y Dragan (1994) ; Brandstädt y col. (1994) ; Brandstädt y col. (1998) ; Brandstädt, Le y Spinrad (1999)
- ^ Dragan (1989) ; Dragan, Prisacaru y Chepoi (1992) ; Dragan (1993)
- ^ Gutiérrez y Oubina (1996) ; Szwarcfiter y Bornstein (1994)
- ^ Brandstädt y col. (1993) ; Brandstädt, Chepoi y Dragan (1998) ; Brandstädt y col. (1998) ; Dragan, Prisacaru y Chepoi (1992) ; Dragan (1993)
- ^ Brandstädt, Chepoi y Dragan (1998) ; Dragan (1989)
- ^ Brandstädt, Chepoi y Dragan (1998) ; Dragan, Prisacaru y Chepoi (1992) ; Dragan (1993)
Referencias
- Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), "El uso algorítmico de la estructura de hiperárbol y el orden máximo de vecindad", Matemáticas aplicadas discretas , 82 : 43–77, doi : 10.1016 / s0166-218x (97) 00125-x.
- Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), "Árboles de aproximación de distancia 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 (1993), "Dually Chordal Graphs", Lecture Notes in Computer Science , 790 : 237-251.
- Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics , 11 : 437–455, doi : 10.1137 / s0895480193253415.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, 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", Lecture Notes in Computer Science , 7676 : 267–277, arXiv : 1207.0953.
- Brešar, Boštjan (2003), "Gráficos de intersección de hipercubos máximos", European Journal of Combinatorics , 24 : 195-209, doi : 10.1016 / s0195-6698 (02) 00142-7.
- De Caria, Pablo; Gutiérrez, Marisa (2012), "Sobre los separadores de vértices mínimos de gráficos dualmente cordales: propiedades y caracterizaciones", Matemáticas aplicadas discretas , 160 : 2627–2635, doi : 10.1016 / j.dam.2012.02.022.
- Dragan, Feodor (1989), Centros de gráficos y la propiedad Helly (en ruso) , Ph.D. tesis, Universidad Estatal de Moldova, Moldova.
- Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Problemas de ubicación en gráficos y la propiedad Helly (en ruso)", Matemáticas discretas. (Moscú) , 4 : 67–73.
- Dragan, Feodor (1993), "Gráficos HT: centros, dominación r conectada y árboles Steiner", Comput. Sci. J. of Moldova (Kishinev) , 1 : 64–83.
- Gutiérrez, Marisa; Oubina, L. (1996), "Caracterizaciones métricas de gráficos de intervalo adecuados y gráficos de grupos de árboles", Journal of Graph Theory , 21 : 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 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), "Clique Graphs of Chordal and Path Graphs", SIAM Journal on Discrete Mathematics , 7 : 331–336, CiteSeerX 10.1.1.52.521 , doi : 10.1137 / s0895480191223191.