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

dc.creatorBonomo, Flavia
dc.creatorFigueiredo, Celina de
dc.creatorDurán Maggiolo, Guillermo
dc.creatorGrippo, Luciano
dc.creatorSafe, Martín
dc.creatorSzwarcfiter, Jayme
dc.date.accessioned2015-08-04T19:17:51Z
dc.date.available2015-08-04T19:17:51Z
dc.date.created2015-08-04T19:17:51Z
dc.date.issued2015
dc.identifierDiscrete Mathematics and Theoretical Computer Science Volumen: 17 Número: 1 Páginas: 187-200
dc.identifier1462-7264
dc.identifierhttps://repositorio.uchile.cl/handle/2250/132358
dc.description.abstractGiven 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.
dc.languageen_US
dc.publisherDiscrete Mathematics and Theoretical Computer Science
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile
dc.subject2-clique graphs
dc.subjectDiamond-free graphs
dc.subjectProbe graphs
dc.titleOn probe 2-clique graphs and probe diamond-free graphs
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución