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