On probe 2-clique graphs and probe diamond-free graphs
Flavia Bonomo (1) (2), Celina M. H. Figueiredo (3), Guillermo Duran (2) (4) (5) (6), Luciano N. Grippo (7), Martín D. Safe (7), Jayme L. Szwarcfiter (3) (8)
(1) Departamento de Computación [Buenos Aires]
(2) Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
(3) Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
(4) Departamento de Matemática [Buenos Aires]
(5) Departamento de Ingenieria Industrial [Santiago]
On probe 2-clique graphs and probe diamond-free graphs
Flavia Bonomo (1) (2), Celina M. H. Figueiredo (3), Guillermo Duran (2) (4) (5) (6), Luciano N. Grippo (7), Martín D. Safe (7), Jayme L. Szwarcfiter (3) (8)
(1) Departamento de Computación [Buenos Aires]
(2) Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
(3) Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
(4) Departamento de Matemática [Buenos Aires]
(5) Departamento de Ingenieria Industrial [Santiago]
(6) Instituto de Cálculo [Buenos Aires]
(7) Instituto de Ciencias [Los Polvorines]
(8) Nucleo de Computação Eletrônica
Abstract
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.
