1. Probe interval and probe unit interval graphs on superclasses of cographs.
- Author
-
Durán, Guillermo, Grippo, Luciano N., and Safe, Martín D.
- Subjects
TREE graphs ,SET theory ,DNA ,HUMAN gene mapping ,HUMAN genome ,MATHEMATICAL analysis - Abstract
Abstract: Probe (unit) interval graphs form a superclass of (unit) interval graphs. 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 interval graphs were introduced by Zhang for an application concerning with the physical mapping of DNA in the human genome project. In this work, we present characterizations by minimal forbidden induced subgraphs of probe interval and probe unit interval graphs within two superclasses of cographs: P
4 -tidy graphs and tree-cographs. [Copyright &y& Elsevier]- Published
- 2011
- Full Text
- View/download PDF