On minimal vertex separators of dually chordal graphs: properties and characterizations
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 ever...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/83624 |
| Aporte de: |
| id |
I19-R120-10915-83624 |
|---|---|
| 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 Chordal Clique Dually chordal Neighborhood Separator Tree |
| spellingShingle |
Matemática Chordal Clique Dually chordal Neighborhood Separator Tree De Caria, Pablo Jesús Gutiérrez, Marisa On minimal vertex separators of dually chordal graphs: properties and characterizations |
| topic_facet |
Matemática Chordal Clique Dually chordal Neighborhood Separator Tree |
| 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. |
| 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 minimal vertex separators of dually chordal graphs: properties and characterizations |
| title_short |
On minimal vertex separators of dually chordal graphs: properties and characterizations |
| title_full |
On minimal vertex separators of dually chordal graphs: properties and characterizations |
| title_fullStr |
On minimal vertex separators of dually chordal graphs: properties and characterizations |
| title_full_unstemmed |
On minimal vertex separators of dually chordal graphs: properties and characterizations |
| title_sort |
on minimal vertex separators of dually chordal graphs: properties and characterizations |
| publishDate |
2012 |
| url |
http://sedici.unlp.edu.ar/handle/10915/83624 |
| work_keys_str_mv |
AT decariapablojesus onminimalvertexseparatorsofduallychordalgraphspropertiesandcharacterizations AT gutierrezmarisa onminimalvertexseparatorsofduallychordalgraphspropertiesandcharacterizations |
| bdutipo_str |
Repositorios |
| _version_ |
1764820488840806400 |