Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
dc.contributor.author
Grippo, Luciano Norberto
dc.contributor.author
Milanič, Martin
dc.contributor.author
Safe, Martin Dario
dc.date.available
2018-08-15T04:08:01Z
dc.date.issued
2016-01
dc.identifier.citation
Bonomo, Flavia; Grippo, Luciano Norberto; Milanič, Martin; Safe, Martin Dario; Graph classes with and without powers of bounded clique-width; Elsevier Science; Discrete Applied Mathematics; 199; 1-2016; 3-15
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/55546
dc.description.abstract
We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the kth powers of the graphs are of clique-width at most ℓ. We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k, there exists a graph class such that the kth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Clique-Width
dc.subject
Hereditary Graph Class
dc.subject
Power of A Graph
dc.subject
Power-Bounded Clique-Width
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Matemática Pura
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Graph classes with and without powers of bounded clique-width
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2018-08-14T14:00:01Z
dc.journal.volume
199
dc.journal.pagination
3-15
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas ; Argentina
dc.description.fil
Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Milanič, Martin. University Of Primorska; Eslovenia
dc.description.fil
Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento; Argentina
dc.journal.title
Discrete Applied Mathematics
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2015.06.010
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X15002966
Archivos asociados