Proper Hamiltonian Paths in Edge-Coloured Multigraphs

Autor:	Raquel Águeda, Yannis Manoussakis, Marina Groshaus, Valentin Borozan, Gervais Mendy, Leandro Montero
Rok vydání:	2017
Předmět:	FOS: Computer and information sciences Discrete Mathematics (cs.DM) Astrophysics::Cosmology and Extragalactic Astrophysics 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics symbols.namesake Computer Science::Discrete Mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Astrophysics::Galaxy Astrophysics Mathematics Hamiltonian path problem Discrete mathematics Mathematics::Combinatorics 010102 general mathematics Multigraph Rainbow Hamiltonian path Route inspection problem Edge coloring 010201 computation theory & mathematics symbols Combinatorics (math.CO) Hamiltonian (quantum mechanics) Computer Science - Discrete Mathematics
Zdroj:	Graphs and Combinatorics. 33:617-633
ISSN:	1435-5914 0911-0119
Popis:	Given a $c$-edge-coloured multigraph, 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 as the number of edges, the number of colours, the rainbow degree and the connectivity. 21 pages
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3d4d7db8268c05c4dff5f9e52781b230 https://doi.org/10.1007/s00373-017-1803-6 Zobrazit plný text záznamu Plný text ve formátu PDF