On probe 2-clique graphs and probe diamond-free graphs | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | Universidad de Chile | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento. Instituto de Ciencias | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento. Instituto de Ciencias | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Figueiredo, Celina M. H. de | |
| dc.contributor.author | Duran, Guillermo Alfredo | |
| dc.contributor.author | Grippo, Luciano Norberto | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.contributor.author | Szwarcfiter, Jayme L. | |
| dc.date.issued | 2015-03 | |
| dc.description.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. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Figueiredo, Celina M. H. de. Universidade Federal do Rio de Janeiro; Brasil | |
| dc.description.fil | Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Figueiredo, Celina M. H. de; Duran, Guillermo Alfredo; Grippo, Luciano Norberto; Safe, Martin Dario; et al.; On probe 2-clique graphs and probe diamond-free graphs; Chapman & Hall; Discrete Mathematics and Theoretical Computer Science; 17; 1; 3-2015; 187-200 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 1365-8050 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/21313 | |
| dc.journal.ciudad | Londres | es |
| dc.journal.number | 1 | es |
| dc.journal.pagination | 187-200 | es |
| dc.journal.pais | Reino Unido | es |
| dc.journal.title | Discrete Mathematics and Theoretical Computer Science | es |
| dc.journal.volume | 17 | es |
| dc.language.iso | eng | es |
| dc.publisher | Chapman & Hall | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/download/2546/4672.pdf | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | 2-Clique Graphs | es |
| dc.subject | Diamond-Free Graphs | es |
| dc.subject | Probe Graphs | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | On probe 2-clique graphs and probe diamond-free graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.22755.pdf
- Tamaño:
- 281.29 KB
- Formato:
- Adobe Portable Document Format
- Descripción: