On probe co-bipartite and probe diamond-free graphs
Flavia Bonomo, Celina Miraglia Herrera de Figueiredo, Guillermo Alfredo Durán, Luciano Norberto Grippo, Martín Darío Safe, Jayme Luiz Szwarcfiter
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.
Full Text: PDF PostScript