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
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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n7_p621_Lin_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0166218X_v159_n7_p621_Lin_oai
record_format dspace
spelling I28-R145-paper_0166218X_v159_n7_p621_Lin_oai2024-08-16 Lin, M.C. Rautenbach, D. Soulignac, F.J. Szwarcfiter, J.L. 2011 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2011;159(7):621-627 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 Powers of cycles, powers of paths, and distance graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n7_p621_Lin_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (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 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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n7_p621_Lin_oai
work_keys_str_mv AT linmc powersofcyclespowersofpathsanddistancegraphs
AT rautenbachd powersofcyclespowersofpathsanddistancegraphs
AT soulignacfj powersofcyclespowersofpathsanddistancegraphs
AT szwarcfiterjl powersofcyclespowersofpathsanddistancegraphs
_version_ 1809356812077498368

Ejemplares similares