Cycles of given color patterns

✍ Scribed by Manoussakis, Y.; Spyratos, M.; Tuza, Zs.

• Book ID: 102648160
• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 634 KB
• Volume: 21
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199602)21:2<153::aid-jgt4>3.0.co;2-q

✦ Synopsis

In 2-edge-colored graphs, w e define an (s, t)-cycle to be a cycle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here w e investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph KE on n vertices. In particular, in the first result w e give a complete characterization for the existence of (s, t)-cycles in Kg 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, w e show that KE contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A.