dc.creatorLin, Min Chih
dc.creatorRautenbach, Dieter
dc.creatorSoulignac, Francisco Juan
dc.creatorSzwarcfiter, Jayme Luiz
dc.date.accessioned2019-01-14T20:47:10Z
dc.date.accessioned2022-10-15T00:15:37Z
dc.date.available2019-01-14T20:47:10Z
dc.date.available2022-10-15T00:15:37Z
dc.date.created2019-01-14T20:47:10Z
dc.date.issued2011-04
dc.identifierLin, Min Chih; Rautenbach, Dieter; Soulignac, Francisco Juan; Szwarcfiter, Jayme Luiz; Powers of cycles, powers of paths, and distance graphs; Elsevier Science; Discrete Applied Mathematics; 159; 7; 4-2011; 621-627
dc.identifier0166-218X
dc.identifierhttp://hdl.handle.net/11336/68005
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/4323640
dc.description.abstractIn 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions.
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2010.03.012
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X10001186
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectCirculant Graph
dc.subjectCircular Arc Graph
dc.subjectCycle
dc.subjectDistance Graph
dc.subjectInterval Graph
dc.subjectPath
dc.titlePowers of cycles, powers of paths, and distance graphs
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución