Determining what sets of trees can be the clique trees of a chordal graph

Chordal graphs have characteristic tree representations, the clique trees. The problems of finding one or enumerating them have already been solved in a satisfactory way. In this paper, the following related problem is studied: given a family T of trees, all having the same vertex set V, determine w...

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:
Matemática
Ciencias Exactas
Chordal graph
Clique
Clique tree
Minimal separator
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/97141
https://ri.conicet.gov.ar/11336/81353
http://link.springer.com/article/10.1007%2Fs13173-011-0048-0
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-97141
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
Ciencias Exactas
Chordal graph
Clique
Clique tree
Minimal separator
spellingShingle Matemática
Ciencias Exactas
Chordal graph
Clique
Clique tree
Minimal separator
De Caria, Pablo Jesús
Gutiérrez, Marisa
Determining what sets of trees can be the clique trees of a chordal graph
topic_facet Matemática
Ciencias Exactas
Chordal graph
Clique
Clique tree
Minimal separator
description Chordal graphs have characteristic tree representations, the clique trees. The problems of finding one or enumerating them have already been solved in a satisfactory way. In this paper, the following related problem is studied: given a family T of trees, all having the same vertex set V, determine whether there exists a chordal graph whose set of clique trees equals T. For that purpose, we undertake a study of the structural properties, some already known and some new, of the clique trees of a chordal graph and the characteristics of the sets that induce subtrees of every clique tree. Some necessary and sufficient conditions and examples of how they can be applied are found, eventually establishing that a positive or negative answer to the problem can be obtained in polynomial time. If affirmative, a graph whose set of clique trees equals T is also obtained. Finally, all the chordal graphs with set of clique trees equal to T are characterized.
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 Determining what sets of trees can be the clique trees of a chordal graph
title_short Determining what sets of trees can be the clique trees of a chordal graph
title_full Determining what sets of trees can be the clique trees of a chordal graph
title_fullStr Determining what sets of trees can be the clique trees of a chordal graph
title_full_unstemmed Determining what sets of trees can be the clique trees of a chordal graph
title_sort determining what sets of trees can be the clique trees of a chordal graph
publishDate 2011
url http://sedici.unlp.edu.ar/handle/10915/97141
https://ri.conicet.gov.ar/11336/81353
http://link.springer.com/article/10.1007%2Fs13173-011-0048-0
work_keys_str_mv AT decariapablojesus determiningwhatsetsoftreescanbethecliquetreesofachordalgraph
AT gutierrezmarisa determiningwhatsetsoftreescanbethecliquetreesofachordalgraph
bdutipo_str Repositorios
_version_ 1764820492401770496

Ejemplares similares