Articulo
On the correspondence between tree representations of chordal and dually chordal graphs
Autor
De Caria, Pablo Jesús
Gutiérrez, Marisa
Institución
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. Facultad de Ciencias Exactas
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
On the correspondence between tree representations of chordal and dually chordal graphs
de Caria, Pablo Jesús; Gutierrez, Marisa (Elsevier, 2014-02)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 ... -
Neighborhood inclusion posets and tree representations for chordal and dually chordal graphs
de Caria, Pablo Jesús (Elsevier Science, 2020-07)This paper is motivated by the following problem: given the family ofclique trees of a chordal graph G, determine whether it is also the family of compatible trees of some dually chordal graph H. A relationship isestablished ... -
Comparing trees characteristic to chordal and dually chordal graphs
de Caria, Pablo Jesús; Gutierrez, Marisa (Elsevier, 2011-08-01)Chordal and dually chordal graphs possess characteristic tree representations, namely, clique trees and compatible trees, respectively. The following problem is studied: given a chordal graph G, it has to be determined if ...