On the correspondence between tree representations of chordal and dually chordal graphs

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 t...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: De Caria, Pablo Jesús, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2014
Materias:
Matemática
Basic chordal graph
Chordal graph
Clique tree
Compatible tree
Dually chordal graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/85139
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-85139
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Basic chordal graph
Chordal graph
Clique tree
Compatible tree
Dually chordal graph
spellingShingle Matemática
Basic chordal graph
Chordal graph
Clique tree
Compatible tree
Dually chordal graph
De Caria, Pablo Jesús
Gutiérrez, Marisa
On the correspondence between tree representations of chordal and dually chordal graphs
topic_facet Matemática
Basic chordal graph
Chordal graph
Clique tree
Compatible tree
Dually chordal graph
description 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.
format Articulo
Articulo
author De Caria, Pablo Jesús
Gutiérrez, Marisa
author_facet De Caria, Pablo Jesús
Gutiérrez, Marisa
author_sort De Caria, Pablo Jesús
title On the correspondence between tree representations of chordal and dually chordal graphs
title_short On the correspondence between tree representations of chordal and dually chordal graphs
title_full On the correspondence between tree representations of chordal and dually chordal graphs
title_fullStr On the correspondence between tree representations of chordal and dually chordal graphs
title_full_unstemmed On the correspondence between tree representations of chordal and dually chordal graphs
title_sort on the correspondence between tree representations of chordal and dually chordal graphs
publishDate 2014
url http://sedici.unlp.edu.ar/handle/10915/85139
work_keys_str_mv AT decariapablojesus onthecorrespondencebetweentreerepresentationsofchordalandduallychordalgraphs
AT gutierrezmarisa onthecorrespondencebetweentreerepresentationsofchordalandduallychordalgraphs
bdutipo_str Repositorios
_version_ 1764820489003335680

Ejemplares similares