On probe 2-clique graphs and probe diamond-free graphs
Author
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.
General note
Artículo de publicación ISI
Patrocinador
ANPCyT
PICT 2012-1324
UBACyT
20020130100808BA
CONICET (Argentina)
PIP 112-201201-00450CO
Brazilian research agency FAPERJ
Brazilian research agency CNPq
FONDECyT
1140787
Millennium Science Institute "Complex Engineering Systems" (Chile)
Brazilian research agency CAPES
Quote Item
Discrete Mathematics and Theoretical Computer Science Volumen: 17 Número: 1 Páginas: 187-200
Collections
The following license files are associated with this item: