Artículo
On the correspondence between tree representations of chordal and dually chordal graphs
Fecha de publicación:
02/2014
Editorial:
Elsevier
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Chordal graphs and their clique graphs (called dually chordal graphs) possess characteristic tree representations, namely, the clique tree and the compatible tree, respectively. The following problem is studied: given a chordal graph G, determine if the clique trees of G are exactly the compatible trees of the clique graph of G. This leads to a new subclass of chordal graphs, basic chordal graphs, which is here characterized. The question is also approached backwards: given a dually chordal graph G, we find all the basic chordal graphs with clique graph equal to G. This approach leads to the possibility of considering several properties of clique trees of chordal graphs and finding their counterparts in compatible trees of dually chordal graphs.
Palabras clave:
Chordal Graph
,
Dually Chordal Graph
,
Basic Chordal Graph
,
Clique Tree
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Gutierrez, Marisa; de Caria, Pablo Jesús; On the correspondence between tree representations of chordal and dually chordal graphs; Elsevier; Discrete Applied Mathematics; 164; Part 2; 2-2014; 500-511
Compartir
Altmétricas
Items relacionados
Mostrando titulos relacionados por título, autor y tema.
-
de Caria, Pablo Jesús ; Gutierrez, Marisa (Elsevier Science, 2016-09)
-
de Caria, Pablo Jesús ; McKee, TerryA (University of Zielona Gora, 2014-07)
-
de Caria, Pablo Jesús ; Gutierrez, Marisa (Elsevier, 2011-08-01)