标题：Rainbow Hamiltonian cycles in strongly edge-colored graphs
作者：Cheng, Yangyang; Sun, Qiang; Tan, Ta Sheng; Wang, Guanghui
作者机构：[Cheng, Yangyang; Wang, Guanghui] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China.; [Sun, Qiang] Yangzhou Univ, Sch Math Sci, Yangz 更多
通讯作者地址：[Wang, GH]Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China.
关键词：Rainbow hamiltonian cycle; Strongly edge-colored graph; Dirac's theorem;; Degree condition
摘要：The classical Dirac's theorem states that every graph G with order at least 3 and minimum degree delta(G) >= vertical bar G vertical bar/2 contains a Hamiltonian cycle. Let G be an edge-colored graph. A subgraph of an edge-colored graph is called rainbow if all its edges have different colors. In 1980 Hahn conjectured that every properly edge-colored complete graph K-n has a rainbow Hamiltonian path. Although this conjecture turns out to be false, it is widely believed that such a coloring always contains a rainbow cycle of length at least n - 2. Inspired by this conjecture, we consider the existence of rainbow Hamiltonian cycles in strongly edge-colored graphs. A strongly edge-colored graph is an edge-colored graph such that every path of length 3 is rainbow, namely, every monochromatic subgraph is an induced matching. We prove that every strongly edge-colored graph G with minimum degree delta(G) >= 2 vertical bar G vertical bar/3 contains a rainbow Hamiltonian cycle. We also prove that every strongly edge-colored graph G with minimum degree delta(G) >= vertical bar G vertical bar/2 contains a rainbow spanning tree. (C) 2019 Elsevier B.V. All rights reserved.