Artículo

Águeda, R.; Borozan, V.; Groshaus, M.; Manoussakis, Y.; Mendy, G.; Montero, L. "Proper Hamiltonian Paths in Edge-Coloured Multigraphs" (2017) Graphs and Combinatorics. 33(4):617-633
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Given a c-edge-coloured multigraph, where c is a positive integer, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters such as the number of edges, the number of colours, the rainbow degree and the connectivity. © 2017, Springer Japan.

Registro:

Documento: Artículo
Título:Proper Hamiltonian Paths in Edge-Coloured Multigraphs
Autor:Águeda, R.; Borozan, V.; Groshaus, M.; Manoussakis, Y.; Mendy, G.; Montero, L.
Filiación:Departamento de Análisis Económico y Finanzas, Universidad de Castilla-La Mancha, Toledo, 45071, Spain
L.R.I., Bât. 650, Université Paris-Sud, Orsay Cedex, 91405, France
Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Edge-coloured graph; Multigraph; Proper Hamiltonian path
Año:2017
Volumen:33
Número:4
Página de inicio:617
Página de fin:633
DOI: http://dx.doi.org/10.1007/s00373-017-1803-6
Título revista:Graphs and Combinatorics
Título revista abreviado:Graphs Comb.
ISSN:09110119
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v33_n4_p617_Agueda

Referencias:

  • Abouelaoualim, A., Das, K.C., Fernandez de la Vega, W., Karpinski, M., Manoussakis, Y., Martinhon, C.A., Saad, R., Cycles and paths in edge-colored graphs with given degrees (2010) J. Graph Theory, 64, pp. 63-86
  • Bang-Jensen, J., Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: a survey (1997) Discret. Math., 165-166, pp. 39-60. , (Graphs and combinatorics (Marseille, 1995))
  • Bang-Jensen, J., Gutin, G., (2001) Digraphs, , Springer, London
  • Bánkfalvi, M., Bánkfalvi, Z., Alternating Hamiltonian circuit in two-coloured complete graphs (1968) Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 11-18. , Academic Press, New York
  • Benkouar, A., Manoussakis, Y., Paschos, V.T., Saad, R., Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results (1996) RAIRO Rech. Opér., 30 (4), pp. 417-438
  • Byer, O.D., Smeltzer, D.L., Edge bounds in nonhamiltonian k -connected graphs (2007) Discret. Math., 307 (13), pp. 1572-1579
  • Feng, J., Giesen, H.E., Guo, Y., Gutin, G., Jensen, T., Rafiey, A., Characterization of edge-colored complete graphs with properly colored Hamilton paths (2006) J. Graph Theory, 53 (4), pp. 333-346
  • Montero, L., Graphs and colors: edge-colored graphs, edge-colorings and proper connections. Ph.D. thesis (2012) University Paris-Sud, 11. , Orsay, France
  • Pevzner, P.A., (2000) Computational Molecular Biology, , MIT Press, Cambridge

Citas:

---------- APA ----------
Águeda, R., Borozan, V., Groshaus, M., Manoussakis, Y., Mendy, G. & Montero, L. (2017) . Proper Hamiltonian Paths in Edge-Coloured Multigraphs. Graphs and Combinatorics, 33(4), 617-633.
http://dx.doi.org/10.1007/s00373-017-1803-6
---------- CHICAGO ----------
Águeda, R., Borozan, V., Groshaus, M., Manoussakis, Y., Mendy, G., Montero, L. "Proper Hamiltonian Paths in Edge-Coloured Multigraphs" . Graphs and Combinatorics 33, no. 4 (2017) : 617-633.
http://dx.doi.org/10.1007/s00373-017-1803-6
---------- MLA ----------
Águeda, R., Borozan, V., Groshaus, M., Manoussakis, Y., Mendy, G., Montero, L. "Proper Hamiltonian Paths in Edge-Coloured Multigraphs" . Graphs and Combinatorics, vol. 33, no. 4, 2017, pp. 617-633.
http://dx.doi.org/10.1007/s00373-017-1803-6
---------- VANCOUVER ----------
Águeda, R., Borozan, V., Groshaus, M., Manoussakis, Y., Mendy, G., Montero, L. Proper Hamiltonian Paths in Edge-Coloured Multigraphs. Graphs Comb. 2017;33(4):617-633.
http://dx.doi.org/10.1007/s00373-017-1803-6