Artículo
Probe interval graphs and probe unit interval graphs on superclasses of cographs
Fecha de publicación:
08/2013
Editorial:
Discrete Mathematics Theoretical Computer Science
Revista:
Discrete Mathematics and Theoretical Computer Science
ISSN:
1365-8050
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non–(probe G) graphs with disconnected complement for every graph class G with a companion.
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"
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Articulos de SEDE CENTRAL
Citación
Bonomo, Flavia; Duran, Guillermo Alfredo; Grippo, Luciano Norberto; Safe, Martin Dario; Probe interval graphs and probe unit interval graphs on superclasses of cographs; Discrete Mathematics Theoretical Computer Science; Discrete Mathematics and Theoretical Computer Science; 15; 2; 8-2013; 177-194
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)