Artículos de revistas
On the correspondence between tree representations of chordal and dually chordal graphs
Fecha
2014-02Registro en:
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
0166-218X
CONICET Digital
CONICET
Autor
de Caria, Pablo Jesús
Gutierrez, Marisa
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.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
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 ... -
Special eccentric vertices for chordal and dually chordal graphs and related classes
De Caria, Pablo Jesús; Gutiérrez, Marisa