Comparing trees characteristic to chordal and dually chordal graphs

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 the clique trees of G are exactly the compatible trees of K(G). This does not...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: De Caria, Pablo Jesús, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2011
Materias:
Ciencias Exactas
Matemática
chordal graph
dually chordal graph
clique tree
compatible tree
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/162528
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-162528
record_format dspace
spelling I19-R120-10915-1625282024-02-09T04:07:25Z http://sedici.unlp.edu.ar/handle/10915/162528 Comparing trees characteristic to chordal and dually chordal graphs De Caria, Pablo Jesús Gutiérrez, Marisa 2011-08 2024-02-08T17:51:09Z en Ciencias Exactas Matemática chordal graph dually chordal graph clique tree compatible tree 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 the clique trees of G are exactly the compatible trees of K(G). This does not always happen. A necessary and sufficient condition so that it is true, in terms of the minimal vertex separators of the graph, is found. Facultad de Ciencias Exactas Departamento de Matemática Articulo Articulo http://creativecommons.org/licenses/by/4.0/ Creative Commons Attribution 4.0 International (CC BY 4.0) application/pdf 33-38
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
chordal graph
dually chordal graph
clique tree
compatible tree
spellingShingle Ciencias Exactas
Matemática
chordal graph
dually chordal graph
clique tree
compatible tree
De Caria, Pablo Jesús
Gutiérrez, Marisa
Comparing trees characteristic to chordal and dually chordal graphs
topic_facet Ciencias Exactas
Matemática
chordal graph
dually chordal graph
clique tree
compatible tree
description 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 the clique trees of G are exactly the compatible trees of K(G). This does not always happen. A necessary and sufficient condition so that it is true, in terms of the minimal vertex separators of the graph, is found.
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 Comparing trees characteristic to chordal and dually chordal graphs
title_short Comparing trees characteristic to chordal and dually chordal graphs
title_full Comparing trees characteristic to chordal and dually chordal graphs
title_fullStr Comparing trees characteristic to chordal and dually chordal graphs
title_full_unstemmed Comparing trees characteristic to chordal and dually chordal graphs
title_sort comparing trees characteristic to chordal and dually chordal graphs
publishDate 2011
url http://sedici.unlp.edu.ar/handle/10915/162528
work_keys_str_mv AT decariapablojesus comparingtreescharacteristictochordalandduallychordalgraphs
AT gutierrezmarisa comparingtreescharacteristictochordalandduallychordalgraphs
_version_ 1807222397166682112

Ejemplares similares