Proper Hamiltonian Paths in Edge-Colored Multigraphs

详细信息    查看全文

• 作者：Raquel  ; Á ; gueda^a ;   ; ^{raquel.agueda@uclm.es} ; Valentin  ; Borozan^b ;   ; ^valik@lri.fr ; Marina  ; Groshaus^c ;   ; ¹ ;   ; ^{groshaus@dc.uba.ar} ; Yannis  ; Manoussakis^b ;   ; ^{yannis@lri.fr} ; Gervais  ; Mendy^b ;   ; ^{gmendy@lri.fr} ; Leandro  ; Montero^b ;   ; ^{lmontero@lri.fr}
• 关键词：Multigraph ; Proper Hamiltonian Path ; Edge-Coloring
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2011
• 出版时间：1 December 2011
• 年：2011
• 卷：38
• 期：Complete
• 页码：5-10
• 全文大小：188 K

文摘

A c-edge-colored multigraph has each edge colored with one of the c available colors and no two parallel edges have the same color. A proper hamiltonian path is a path containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper hamiltonian path, depending on several parameters such as the number of edges, the rainbow degree, etc.