Powers of cycles, powers of paths, and distance graphs

En:

Discrete Appl Math 2011;159(7):621-627

Fecha:

2011

Formato:

application/pdf

Tipo de documento:

info:eu-repo/semantics/article
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion

Descriptores:

Circulant graph -  Circular arc graph -  Cycle -  Distance graph -  Interval graph -  Path -  Circulant graphs -  Circular-arc graph -  Cycle

Descripción:

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.

Identificador(es):

http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n7_p621_Lin

Derechos:

info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by/2.5/ar