Probe interval graphs and probe unit interval graphs on superclasses of cographs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.177--194
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980766
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:49
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:27:44

Fichier

2124-8275-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980766, version 1

Collections

Citation

Flavia Bonomo, Guillermo Durán, Luciano N. Grippo, Martın D. Safe. Probe interval graphs and probe unit interval graphs on superclasses of cographs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.177--194. 〈hal-00980766〉

Partager

Métriques

Consultations de la notice

719

Téléchargements de fichiers

232