Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.dam.2010.03.012 | Discrete Applied Mathematics |
Keywords | Field | DocType |
characterizations lead,distance graph,circulant graph,recognition algorithm,interval graph,. cycle,circular arc graph,additional restriction,well-known circulant graph,path,polynomial-time recognition algorithm,structural characterization,recognition problem,cycle,linear time,polynomial time | Graph,Discrete mathematics,Circulant graph,Indifference graph,Combinatorics,Interval graph,Chordal graph,Circulant matrix,Circular-arc graph,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
159 | 7 | Discrete Applied Mathematics |
Citations | PageRank | References |
8 | 0.49 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Dieter Rautenbach | 2 | 946 | 138.87 |
| Francisco Juan Soulignac | 3 | 8 | 0.49 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |