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: JOUR
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 todo:paper_0166218X_v159_n7_p621_Lin
record_format dspace
spelling todo:paper_0166218X_v159_n7_p621_Lin2023-10-03T15:03:39Z Powers of cycles, powers of paths, and distance graphs 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. JOUR 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)
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 JOUR
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
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_ 1807321983821545472

Ejemplares similares