Premium
Cycles of given color patterns
Author(s) -
Manoussakis Y.,
Spyratos M.,
Tuza Zs.
Publication year - 1996
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/(sici)1097-0118(199602)21:2<153::aid-jgt4>3.0.co;2-q
Subject(s) - combinatorics , mathematics , colored , graph , hamiltonian path , enhanced data rates for gsm evolution , hamiltonian (control theory) , discrete mathematics , computer science , artificial intelligence , mathematical optimization , materials science , composite material
In 2‐edge‐colored graphs, we define an ( s, t )‐cycle to be a cyle of length s + t , in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of ( s, t )‐cycles, in a 2‐edge‐colored complete graph K c n on n vertices. In particular, in the first result we give a complete characterization for the existence of ( s, t )‐cycles in K c n with n relatively large with respect to max({ s, t }). We also study cycles of length 4 for all possible values of s and t . Then, we show that K c n contains an ( s, t )‐hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [ Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of ( s , 1)‐cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.