Cycles and paths in edge‐colored graphs with given degrees
Cycles and paths in edge‐colored graphs with given degrees
复制标题
DOI：
10.1002/jgt.20440
复制
发表时间：
2010-05
影响因子：
0.9
通讯作者：
A. Abouelaoualim;K. Das;W. F. D. L. Vega;Marek Karpinski;Y. Manoussakis;C. Martinhon;R. Saad
中科院分区：
文献类型：
--
作者：
A. Abouelaoualim;K. Das;W. F. D. L. Vega;Marek Karpinski;Y. Manoussakis;C. Martinhon;R. Saad
Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ⌈(n+1)/2⌉ has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010
