| dc.creator | De Caria, Pablo Jesús | |
| dc.creator | Gutiérrez, Marisa | |
| dc.date | 2012 | |
| dc.date | 2019-10-18T17:20:59Z | |
| dc.identifier | http://sedici.unlp.edu.ar/handle/10915/83624 | |
| dc.identifier | issn:0166-218X | |
| dc.description | Many works related to dually chordal graphs, their cliques and neighborhoods were published by Brandstädt et al. (1998) and Gutierrez (1996). We will undertake a similar study by considering minimal vertex separators and their properties instead. We find a necessary and sufficient condition for every minimal vertex separator to be contained in the closed neighborhood of a vertex and two major characterizations of dually chordal graphs are proved. The first states that a graph is dually chordal if and only if it possesses a spanning tree such that every minimal vertex separator induces a subtree. The second says that a graph is dually chordal if and only if the family of minimal vertex separators is Helly, its intersection graph is chordal and each of its members induces a connected subgraph. We also found adaptations for them, requiring just O(|E(G)|) minimal vertex separators if they are conveniently chosen. We obtain at the end a proof of a known characterization of the class of hereditary dually chordal graphs that relies on the properties of minimal vertex separators. | |
| dc.description | Facultad de Ciencias Exactas | |
| dc.format | application/pdf | |
| dc.format | 2627-2635 | |
| dc.language | en | |
| dc.rights | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
| dc.rights | Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
| dc.subject | Matemática | |
| dc.subject | Chordal | |
| dc.subject | Clique | |
| dc.subject | Dually chordal | |
| dc.subject | Neighborhood | |
| dc.subject | Separator | |
| dc.subject | Tree | |
| dc.title | On minimal vertex separators of dually chordal graphs: properties and characterizations | |
| dc.type | Articulo | |
| dc.type | Articulo | |
