On probe 2-clique graphs and probe diamond-free graphs

被引：0

作者：

Bonomo, Flavia ^{[1
,4
]}

de Figueiredo, Celina M. H. ^{[2
]}

Duran, Guillermo ^{[1
,5
,6
,7
]}

Grippo, Luciano N. ^{[8
]}

Safe, Martin D. ^{[8
]}

Szwarcfiter, Jayme L. ^{[2
,3
]}

机构：

[1] Consejo Nacl Invest Cient & Tecn, RA-1033 Buenos Aires, DF, Argentina

[2] Univ Fed Rio de Janeiro, COPPE, BR-21941 Rio De Janeiro, Brazil

[3] Univ Fed Rio de Janeiro, NCE, BR-21941 Rio De Janeiro, Brazil

[4] Univ Buenos Aires, FCEN, Dept Comp, Buenos Aires, DF, Argentina

[5] Univ Buenos Aires, FCEN, Dept Matemat, Buenos Aires, DF, Argentina

[6] Univ Buenos Aires, FCEN, Inst Calculo, Buenos Aires, DF, Argentina

[7] Univ Chile, FCFM, Dept Ingn Ind, Santiago, Chile

[8] Univ Nacl Gen Sarmiento, Inst Ciencias, Los Polvorines, Argentina

来源：

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | 2015年 / 17卷 / 01期

关键词：

2-clique graphs; diamond-free graphs; probe graphs; RECOGNITION;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.

引用

页码：187 / 200

页数：14

共 19 条

[1] Probe threshold and probe trivially perfect graphs [J].