Powers of cycles, powers of paths, and distance graphs

Lin, Min Chih GND; Rautenbach, Dieter GND; Soulignac, Francisco Juan; Szwarcfiter, Jayme Luiz

In 1988, Golumbic and Hammer characterized 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 colourings 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.

Cite

Citation style:

Lin, Min Chih / Rautenbach, Dieter / Soulignac, Francisco Juan / et al: Powers of cycles, powers of paths, and distance graphs. 2009.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:
All rights reserved

Export