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.

Zitieren

Zitierform:

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

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export