Powers of cycles, powers of paths, and distance graphs |
| |
| Authors: | Min Chih Lin Francisco Juan Soulignac |
| |
| Institution: | a Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentinab Institut für Mathematik, Technische Universität Ilmenau, Postfach 100565, D-98684 Ilmenau, Germanyc Universidade Federal do Rio de Janeiro, Instituto de Matemática, NCE and COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| |
| 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. |
| |
| Keywords: | Cycle Path Circulant graph Distance graph Circular arc graph Interval graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
