标题: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
通讯作者地址:[Wang, GH]Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China.
来源:DISCRETE MATHEMATICS
出版年:2019
卷:342
期:4
页码:1186-1190
DOI:10.1016/j.disc.2019.01.002
关键词: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.
收录类别:SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85060243147&doi=10.1016%2fj.disc.2019.01.002&partnerID=40&md5=8db9b5c2b2388c29c2b3c8a5787d5197
TOP