Premium
Cycles and paths in edge‐colored graphs with given degrees
Author(s) -
Abouelaoualim, A.,
Das K. Ch.,
de la Vega W. Fernandez,
Karpinski M.,
Manoussakis Y.,
Martinhon C. A.,
Saad R.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20440
Subject(s) - colored , multigraph , combinatorics , mathematics , hamiltonian path , edge coloring , graph , hamiltonian (control theory) , enhanced data rates for gsm evolution , discrete mathematics , line graph , graph power , computer science , mathematical optimization , telecommunications , materials science , composite material
Abstract 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