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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2011-04, Vol.159 (7), p.621-627
Main Authors: Lin, Min Chih, Rautenbach, Dieter, Soulignac, Francisco Juan, Szwarcfiter, Jayme Luiz
Format: Article
Language:English
Subjects:
Algorithms
Circulant graph
Circular arc graph
Coloring
Constrictions
Cycle
Distance graph
Graphs
Hammers
Interval graph
Mathematical analysis
Path
Recognition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2010.03.012