Flavia Bonomo ; Guillermo Durán ; Luciano N. Grippo ; Martın D. Safe - Probe interval graphs and probe unit interval graphs on superclasses of cographs

dmtcs:602 - Discrete Mathematics & Theoretical Computer Science, August 21, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.602
Probe interval graphs and probe unit interval graphs on superclasses of cographs

Authors: Flavia Bonomo 1,2; Guillermo Durán 1,3,4; Luciano N. Grippo 5; Martın D. Safe

  • 1 Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
  • 2 Departamento de Computación [Buenos Aires]
  • 3 Departamento de Matemática [Buenos Aires]
  • 4 Departamento de Ingenieria Industrial [Santiago]
  • 5 Instituto de Ciencias [Los Polvorines]

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.

Volume: Vol. 15 no. 2
Section: Graph Theory
Published on: August 21, 2013
Accepted on: June 9, 2015
Submitted on: March 26, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 648 times.
This article's PDF has been downloaded 313 times.