TY - JOUR
T1 - A note on equitable Hamiltonian cycles
AU - Ophelders, Tim
AU - Lambers, Roel
AU - Spieksma, Frits C.R.
AU - Vredeveld, Tjark
PY - 2021/11/15
Y1 - 2021/11/15
N2 - Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists.
AB - Given a complete graph with an even number of vertices, and with each edge colored with one of two colors (say red or blue), an equitable Hamiltonian cycle is a Hamiltonian cycle that can be decomposed into two perfect matchings such that both perfect matchings have the same number of red edges. We show that, for any coloring of the edges, in any complete graph on at least 6 vertices, an equitable Hamiltonian cycle exists.
KW - Colored complete graphs
KW - Equitable Hamiltonian cycle
KW - Local search
KW - Polynomial time algorithm
UR - http://www.scopus.com/inward/record.url?scp=85089978709&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2020.08.023
DO - 10.1016/j.dam.2020.08.023
M3 - Article
AN - SCOPUS:85089978709
VL - 303
SP - 127
EP - 136
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - XX
ER -