En el área matemática de la teoría de grafos , un grafo bipartito cordal es un grafo bipartito B = ( X , Y , E ) en el que cada ciclo de longitud de al menos 6 en B tiene una cuerda , es decir, una arista que conecta dos vértices que son una distancia> 1 entre sí en el ciclo. [1] Un mejor nombre sería débilmente cordal y bipartito ya que los grafos bipartitos cordales en general no son cordales como muestra el ciclo inducido de longitud 4.
Caracterizaciones
Los gráficos bipartitos de cuerdas tienen varias caracterizaciones en términos de ordenamientos de eliminación perfectos , hipergráficos y matrices . Están estrechamente relacionados con grafos fuertemente cordales . Por definición, los grafos bipartitos cordales tienen una caracterización de subgrafo prohibido como los grafos que no contienen ningún ciclo inducido de longitud 3 o de longitud al menos 5 (los llamados huecos) como subgrafo inducido . Por lo tanto, una gráfica G es bipartita cordal si y solo si G no tiene triángulos ni huecos. En Golumbic (1980) , se mencionan otras dos caracterizaciones: B es bipartito cordal si y solo si cada separador de borde mínimo induce un subgrafo bipartito completo en B si y solo si cada subgrafo inducido es bipartito de eliminación perfecta.
Martin Farber ha demostrado: Un grafo es fuertemente cordal si y solo si el grafo de incidencia bipartito de su hipergrafia clique es cordal bipartito. [2]
Una caracterización similar es válida para el hipergrama de vecindad cerrada: un gráfico es fuertemente cordal si y solo si el gráfico de incidencia bipartito de su hipergrama de vecindad cerrada es cordal bipartito. [3]
Otro resultado encontrado por Elias Dahlhaus es: Un grafo bipartito B = ( X , Y , E ) es bipartito cordal si y solo si el grafo dividido resultante de hacer de X una camarilla es fuertemente cordal. [4]
Un grafo bipartito B = ( X , Y , E ) es bipartito cordal si y solo si cada subgrafo inducido de B tiene un orden de vecindad X máximo y un orden de vecindad Y máximo. [5]
Varios resultados describen la relación entre los gráficos bipartitos cordales y los hipergráficos de vecindad totalmente equilibrados de los gráficos bipartitos. [6]
En [7] se proporciona una caracterización de los gráficos bipartitos cordales en términos de gráficos de intersección relacionados con los hipergráficos. [7]
Un gráfico bipartito es bipartito cordal si y solo si su matriz de adyacencia está totalmente equilibrada si y solo si la matriz de adyacencia está libre de gamma. [8]
Reconocimiento
Los gráficos bipartitos cordales se pueden reconocer en el tiempo O (min ( n 2 , ( n + m ) log n )) para un gráfico con n vértices y m aristas. [9]
Complejidad de problemas
Varios problemas como el ciclo hamiltoniano, [10] el árbol de Steiner [11] y la dominación eficiente [12] permanecen NP-completos en grafos bipartitos cordales.
Varios otros problemas que se pueden resolver de manera eficiente para los gráficos bipartitos se pueden resolver de manera más eficiente para los gráficos bipartitos cordales, como se explica en [13]
Clases de grafos relacionados
Cada grafo bipartito cordal es un grafo modular . Los gráficos bipartitos cordales incluyen los gráficos bipartitos completos y los gráficos hereditarios de distancia bipartitos . [14]
Notas
- ^ Golumbic (1980) , p. 261, Brandstädt, Le & Spinrad (1999) , Definición 3.4.1, p. 43.
- ^ Farber (1983) ; Brandstädt, Le y Spinrad (1999) , Teorema 3.4.1, pág. 43.
- ↑ Brandstädt (1991)
- ^ Brandstädt, Le y Spinrad (1999) , Corolario 8.3.2, p. 129.
- ^ Dragan y Voloshin (1996)
- ^ Brandstädt, Le & Spinrad (1999) , Teoremas 8.2.5, 8.2.6, págs. 126-127.
- ↑ Huang (2006)
- ↑ Farber (1983)
- ^ Lubiw (1987) ; Paige y Tarjan (1987) ; Spinrad (1993) ; Spinrad (2003) .
- ↑ Müller (1996)
- ^ Müller y Brandstädt (1987)
- ^ Lu y Tang (2002)
- ^ Spinrad (2003) .
- ^ Gráficos bipartitos de cuerdas , sistema de información sobre clases de gráficos y sus inclusiones, consultado el 30 de septiembre de 2016.
Referencias
- Brandstädt, Andreas (1991), "Clases de grafos bipartitos relacionados con grafos cordales", Matemáticas aplicadas discretas , 32 : 51–60, doi : 10.1016 / 0166-218x (91) 90023-p.
- 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.
- Dragan, Feodor; Voloshin, Vitaly (1996), "Gráficos de incidencia de hipergráficos biacíclicos", Matemáticas aplicadas discretas , 68 : 259-266, doi : 10.1016 / 0166-218x (95) 00070-8.
- Farber, M. (1983), "Caracterizaciones de grafos fuertemente cordales", Matemáticas discretas , 43 (2-3): 173-189, doi : 10.1016 / 0012-365X (83) 90154-1.
- Golumbic, Martin Charles (1980), Teoría algorítmica de gráficos y gráficos perfectos , Academic Press, ISBN 0-12-289260-7.
- Huang, Jing (2006), "Caracterizaciones de representación de grafos bipartitos cordales", Journal of Combinatorial Theory, Serie B , 96 (5): 673–683, doi : 10.1016 / j.jctb.2006.01.001.
- Lu, Chin Lung; Tang, Chuan Yi (2002), "Dominación eficiente ponderada en algunos gráficos perfectos", Matemáticas aplicadas discretas , 117 : 163-182, doi : 10.1016 / s0166-218x (01) 00184-6.
- Lubiw, A. (1987), "Doble ordenación léxica de matrices", SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137 / 0216057.
- Müller, Haiko (1996), "Circuitos de Hamilton en grafos bipartitos cordales", Matemáticas discretas , 156 : 291-298, doi : 10.1016 / 0012-365x (95) 00057-4.
- Müller, Haiko; Brandstädt, Andreas (1987), "The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs", Theoretical Computer Science , 53 : 257-265, doi : 10.1016 / 0304-3975 (87) 90067-3.
- Paige, R .; Tarjan, RE (1987), "Tres algoritmos de refinamiento de particiones", SIAM Journal on Computing , 16 (6): 973–989, doi : 10.1137 / 0216062.
- Spinrad, Jeremy (1993), "Doble orden léxico de matrices densas 0-1", Information Processing Letters , 45 (2): 229-235, doi : 10.1016 / 0020-0190 (93) 90209-R.
- Spinrad, Jeremy (2003), Efficient Graph Representations , Fields Institute Monographs, American Mathematical Society, ISBN 0-8218-2815-0.