Powers of cycles, powers of paths, and distance graphs

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, Min Chih, Soulignac, Francisco Juan
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n7_p621_Lin 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	paper:paper_0166218X_v159_n7_p621_Lin
record_format	dspace
spelling	paper:paper_0166218X_v159_n7_p621_Lin2023-06-08T15:15:31Z Powers of cycles, powers of paths, and distance graphs Lin, Min Chih Soulignac, Francisco Juan 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n7_p621_Lin 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, Min Chih Soulignac, Francisco Juan 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.
author	Lin, Min Chih Soulignac, Francisco Juan
author_facet	Lin, Min Chih Soulignac, Francisco Juan
author_sort	Lin, Min Chih
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	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n7_p621_Lin http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin
work_keys_str_mv	AT linminchih powersofcyclespowersofpathsanddistancegraphs AT soulignacfranciscojuan powersofcyclespowersofpathsanddistancegraphs
_version_	1768542077280321536

Powers of cycles, powers of paths, and distance graphs

Ejemplares similares