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:
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile
Related items
Showing items related by title, author, creator and subject.
-
Bonomo, Flavia; Durán Maggiolo, Guillermo; Groshaus, Marina (2007)A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of ...
-
Alcón, Liliana; Bonomo, Flavia; Durán, Guillermo; Gutierrez, Marisa; Mazzoleni, María; Ries, Bernard; Valencia-Pabon, Mario (Elsevier B.V., 2018)Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a ...
-
Gutierrez C., Sequeda J.F. (Association for Computing Machinery, 2020)