Powers of cycles, powers of paths, and distance graphs

Mostrar todas las versiones(3)

In 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 t...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2011
Materias:
Circulant graph
Circular arc graph
Cycle
Distance graph
Interval graph
Path
Circulant graphs
Circular-arc graph
Algorithms
Graphic methods
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0166218X_v159_n7_p621_Lin
record_format dspace
spelling paperaa:paper_0166218X_v159_n7_p621_Lin2023-06-12T16:46:55Z Powers of cycles, powers of paths, and distance graphs Discrete Appl Math 2011;159(7):621-627 Lin, M.C. Rautenbach, D. Soulignac, F.J. Szwarcfiter, J.L. Circulant graph Circular arc graph Cycle Distance graph Interval graph Path Circulant graphs Circular-arc graph Cycle Distance graph Interval graph Path Algorithms Graphic methods Graph theory In 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. © 2010 Elsevier B.V. All rights reserved. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic Circulant graph
Circular arc graph
Cycle
Distance graph
Interval graph
Path
Circulant graphs
Circular-arc graph
Cycle
Distance graph
Interval graph
Path
Algorithms
Graphic methods
Graph theory
spellingShingle Circulant graph
Circular arc graph
Cycle
Distance graph
Interval graph
Path
Circulant graphs
Circular-arc graph
Cycle
Distance graph
Interval graph
Path
Algorithms
Graphic methods
Graph theory
Lin, M.C.
Rautenbach, D.
Soulignac, F.J.
Szwarcfiter, J.L.
Powers of cycles, powers of paths, and distance graphs
topic_facet Circulant graph
Circular arc graph
Cycle
Distance graph
Interval graph
Path
Circulant graphs
Circular-arc graph
Cycle
Distance graph
Interval graph
Path
Algorithms
Graphic methods
Graph theory
description In 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. © 2010 Elsevier B.V. All rights reserved.
format Artículo
Artículo
publishedVersion
author Lin, M.C.
Rautenbach, D.
Soulignac, F.J.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Rautenbach, D.
Soulignac, F.J.
Szwarcfiter, J.L.
author_sort Lin, M.C.
title Powers of cycles, powers of paths, and distance graphs
title_short Powers of cycles, powers of paths, and distance graphs
title_full Powers of cycles, powers of paths, and distance graphs
title_fullStr Powers of cycles, powers of paths, and distance graphs
title_full_unstemmed Powers of cycles, powers of paths, and distance graphs
title_sort powers of cycles, powers of paths, and distance graphs
publishDate 2011
url http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin
work_keys_str_mv AT linmc powersofcyclespowersofpathsanddistancegraphs
AT rautenbachd powersofcyclespowersofpathsanddistancegraphs
AT soulignacfj powersofcyclespowersofpathsanddistancegraphs
AT szwarcfiterjl powersofcyclespowersofpathsanddistancegraphs
_version_ 1769810285015597056

Ejemplares similares