INVESTIGADORES
GRIPPO Luciano Norberto
artículos
Título:
Characterizing interval graphs which are probe unit interval graphs
Autor/es:
GRIPPO, LUCIANO NORBERTO
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2019 vol. 262 p. 83 - 95
ISSN:
0166-218X
Resumen:
A graph is a probe unit interval graph if its vertex set can be partitioned into a set P of probe vertices and a stable set N of nonprobe vertices, so that a unit interval graph can be obtained by adding a set of edges whose endpoints belong to N. A partitioned graph is a graph having a prescribed partition into P and N. In this article we present structural characterizations for those partitioned interval graphs and unpartitioned interval graphs which are probe unit interval graphs, in terms of certain characteristics of their interval models. These characterizations lead to characterizations of probe unit interval graphs within the class of interval graphs by minimal forbidden induced subgraphs.
