Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © 2010 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Powers of cycles, powers of paths, and distance graphs
Autor:Lin, M.C.; Rautenbach, D.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina
Institut für Mathematik, Technische Universitt Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany
Universidade Federal Do Rio de Janeiro, Instituto de Matemática, COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:Circulant graph; Circular arc graph; Cycle; Distance graph; Interval graph; Path; Circulant graphs; Circular-arc graph; Cycle; Distance graph; Interval graph; Path; Algorithms; Graphic methods; Graph theory
Año:2011
Volumen:159
Número:7
Página de inicio:621
Página de fin:627
DOI: http://dx.doi.org/10.1016/j.dam.2010.03.012
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v159_n7_p621_Lin.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n7_p621_Lin

Referencias:

  • Bermond, J.-C., Comellas, F., Hsu, D.F., Distributed loop computer networks: A survey (1985) J. Parallel Distrib. Comput., 24, pp. 2-10
  • Bogart, K.P., West, D.B., A short proof that 'proper = unit' (1999) Discrete Mathematics, 201 (1-3), pp. 21-23. , PII S0012365X98003100
  • Bondy, J.A., Murty, U.S.R., (2008) Graph Theory, , Springer
  • Chang, G.J., Huang, L., Zhu, X., Circular chromatic numbers and fractional chromatic numbers of distance graphs (1998) European Journal of Combinatorics, 19 (4), pp. 423-431
  • Corneil, D.G., A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs (2004) Discrete Appl. Math., 138, pp. 371-379
  • Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P., Simple linear time recognition of unit interval graphs (1995) Inform. Process. Lett., 55, pp. 99-104
  • Deng, X., Hell, P., Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM Journal on Computing, 25 (2), pp. 390-403
  • Deuber, W., Zhu, X., The chromatic number of distance graphs (1997) Discrete Math., 165-166, pp. 195-204
  • Effantin, B., Kheddouci, H., The b-chromatic number of some power graphs (2003) Discrete Math. Theor. Comput. Sci., 6, pp. 45-54
  • Eggleton, R.B., Erds, P., Skilton, D.K., Coloring the real line (1985) J. Combin. Theory Ser. B, 39, pp. 86-100
  • Eggleton, R.B., Erds, P., Skilton, D.K., Colouring prime distance graphs (1990) Graphs Combin., 6, pp. 17-32
  • Evdokimov, S.A., Ponomarenko, I.N., Circulant graphs: Recognizing and isomorphism testing in polynomial time (2004) St. Petersburg Math. J., 15, pp. 813-835
  • Gardi, F., The Roberts characterization of proper and unit interval graphs (2007) Discrete Mathematics, 307 (22), pp. 2906-2908. , DOI 10.1016/j.disc.2006.04.043, PII S0012365X07000696
  • Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press New York, NY
  • Golumbic, M.C., Hammer, P.L., Stability in circular arc graphs (1988) J. Algorithms, 9, pp. 314-320
  • Hell, P., Huang, J., Certifying LexBFS recognition algorithms for proper interval graphs and proper interval digraphs (2004) SIAM Journal on Discrete Mathematics, 18 (3), pp. 554-570. , DOI 10.1137/S0895480103430259
  • Herrera De Figueiredo, C.M., Meidanis, J., Picinin De Mello, C., A linear-time algorithm for proper interval graph recognition (1995) Inform. Process. Lett., 56, pp. 179-184
  • Kaplan, H., Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs (2006) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4271, pp. 289-300. , Graph-Theoretic Concepts in Computer Science - 32nd International Workshop, WG 2006, Revised Papers
  • Kemnitz, A., Kolberg, H., Coloring of integer distance graphs (1998) Discrete Mathematics, 191 (1-3), pp. 113-123. , PII S0012365X98000995
  • Kemnitz, A., Marangio, M., Colorings and list colorings of integer distance graphs (2001) Congr. Numer., 151, pp. 75-84
  • McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37, pp. 93-147
  • Muzychuk, M., A solution of the isomorphism problem for circulant graphs (2004) Proceedings of the London Mathematical Society, 88 (1), pp. 1-41
  • Muzychuk, M., Tinhofer, G., Recognizing circulant graphs of prime order in polynomial time (1998) J. Combin., 5, pp. 347-374
  • Muzychuk, M., Tinhofer, G., Recognizing circulant graphs in polynomial time: An application of association schemes (2001) Electron. J. Combin., 8, pp. 0023R26
  • Ponomarenko, I., Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments (1992) Acta Appl. Math., 29, pp. 139-160
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf., pp. 139-146. , Ann Arbor, Mich., 1968 Academic Press New York
  • Voigt, M., Colouring of distance graphs (1999) Ars Combin., 52, pp. 3-12
  • Voigt, M., Walther, H., Chromatic number of prime distance graphs (1994) Discrete Appl. Math., 51, pp. 197-209

Citas:

---------- APA ----------
Lin, M.C., Rautenbach, D., Soulignac, F.J. & Szwarcfiter, J.L. (2011) . Powers of cycles, powers of paths, and distance graphs. Discrete Applied Mathematics, 159(7), 621-627.
http://dx.doi.org/10.1016/j.dam.2010.03.012
---------- CHICAGO ----------
Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L. "Powers of cycles, powers of paths, and distance graphs" . Discrete Applied Mathematics 159, no. 7 (2011) : 621-627.
http://dx.doi.org/10.1016/j.dam.2010.03.012
---------- MLA ----------
Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L. "Powers of cycles, powers of paths, and distance graphs" . Discrete Applied Mathematics, vol. 159, no. 7, 2011, pp. 621-627.
http://dx.doi.org/10.1016/j.dam.2010.03.012
---------- VANCOUVER ----------
Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L. Powers of cycles, powers of paths, and distance graphs. Discrete Appl Math. 2011;159(7):621-627.
http://dx.doi.org/10.1016/j.dam.2010.03.012