Artículo
On probe 2-clique graphs and probe diamond-free graphs
Bonomo, Flavia
; Figueiredo, Celina M. H. de; Duran, Guillermo Alfredo
; Grippo, Luciano Norberto
; Safe, Martin Dario
; Szwarcfiter, Jayme L.
Fecha de publicación:
03/2015
Editorial:
Chapman & Hall
Revista:
Discrete Mathematics and Theoretical Computer Science
ISSN:
1365-8050
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.
Palabras clave:
2-Clique Graphs
,
Diamond-Free Graphs
,
Probe Graphs
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Citación
Bonomo, Flavia; Figueiredo, Celina M. H. de; Duran, Guillermo Alfredo; Grippo, Luciano Norberto; Safe, Martin Dario; et al.; On probe 2-clique graphs and probe diamond-free graphs; Chapman & Hall; Discrete Mathematics and Theoretical Computer Science; 17; 1; 3-2015; 187-200
Compartir
Items relacionados
Mostrando titulos relacionados por título, autor y tema.
-
Bonomo-Braberman, Flavia; Durán, Guillermo; Safe, Martin Dario ; Wagler, Annegret K. (Elsevier Science, 2020-07-15)
-
de Caria, Pablo Jesús ; Gutierrez, Marisa (Elsevier Science, 2016-09)
-
Bonomo, Flavia ; Duran, Guillermo Alfredo ; Safe, Martin Dario ; Wagler, Annegret Katrin (Discrete Mathematics and Theoretical Computer Science, 2014-03)