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

dc.creatorDe Caria, Pablo Jesús
dc.creatorGutiérrez, Marisa
dc.date2014
dc.date2019-11-07T15:13:05Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/85139
dc.identifierissn:0166-218X
dc.descriptionChordal 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.
dc.descriptionFacultad de Ciencias Exactas
dc.formatapplication/pdf
dc.format500-511
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rightsCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
dc.subjectMatemática
dc.subjectBasic chordal graph
dc.subjectChordal graph
dc.subjectClique tree
dc.subjectCompatible tree
dc.subjectDually chordal graph
dc.titleOn the correspondence between tree representations of chordal and dually chordal graphs
dc.typeArticulo
dc.typeArticulo


Este ítem pertenece a la siguiente institución