Characterizing interval graphs which are probe unit interval graphs

被引：0
作者：
Grippo, Luciano N. [1 ]
机构：
[1] Univ Nacl Gen Sarmiento, Inst Ciencias, Los Polvorines, Buenos Aires, Argentina
来源：
DISCRETE APPLIED MATHEMATICS | 2019年 / 262卷
关键词：
Interval graphs; Unit interval graphs; Probe unit interval graphs; TIME RECOGNITION; ALGORITHM; ORIENTATION;
D O I：
10.1016/j.dam.2019.02.022
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A graph G 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. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码：83 / 95
页数：13
相关论文
共 25 条
[1]  
[Anonymous], 1957, INT MATH NACHR
[2]   ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE [J].
BENZER, S .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1959, 45 (11) :1607-1620
[3]  
Bonomo F, 2013, DISCRETE MATH THEOR, V15, P177
[4]   TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].
BOOTH, KS ;
LUEKER, GS .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379
[5]  
Brown DE, 2006, AUSTRALAS J COMB, V35, P221
[6]  
Chang GJ, 2005, LECT NOTES COMPUT SC, V3404, P521
[7]  
Corneil Derek G., 1998, SODA 1998, P175
[8]   SIMPLE LINEAR-TIME RECOGNITION OF UNIT INTERVAL-GRAPHS [J].
CORNEIL, DG ;
KIM, HY ;
NATARAJAN, S ;
OLARIU, S ;
SPRAGUE, AP .
INFORMATION PROCESSING LETTERS, 1995, 55 (02) :99-104
[9]   A LINEAR-TIME ALGORITHM FOR PROPER INTERVAL GRAPH RECOGNITION [J].
DEFIGUEIREDO, CMH ;
MEIDANIS, J ;
DEMELLO, CP .
INFORMATION PROCESSING LETTERS, 1995, 56 (03) :179-184
[10]   INCIDENCE MATRICES AND INTERVAL GRAPHS [J].
FULKERSON, DR ;
GROSS, OA .
PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+
123