A note on equitable Hamiltonian cycles

Tim Ophelders; Roel Lambers; Frits C.R. Spieksma; Tjark Vredeveld

doi:10.1016/j.dam.2020.08.023

A note on equitable Hamiltonian cycles

Tim Ophelders, Roel Lambers, Frits C.R. Spieksma, Tjark Vredeveld (Corresponding author)

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

172 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	127-136
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	303
Issue number	XX
Early online date	29 Aug 2020
DOIs	https://doi.org/10.1016/j.dam.2020.08.023
Publication status	Published - 15 Nov 2021

Funding

The research of Frits C.R. Spieksma was partly funded by the Netherlands Organization for Scientific Research (NWO) through Gravitation grant NETWORKS 024.002.003 . The research of Tim Ophelders was partly funded by the National Science Foundation (NSF) through grant CCF-1907591 .

Keywords

Colored complete graphs
Equitable Hamiltonian cycle
Local search
Polynomial time algorithm

Access to Document

10.1016/j.dam.2020.08.023

published versionFinal published version, 461 KBLicence: CC BY

Cite this

@article{c1101b0ab7a9437a9e952f15118b59a9,

title = "A note on equitable Hamiltonian cycles",

abstract = "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.",

keywords = "Colored complete graphs, Equitable Hamiltonian cycle, Local search, Polynomial time algorithm",

author = "Tim Ophelders and Roel Lambers and Spieksma, {Frits C.R.} and Tjark Vredeveld",

year = "2021",

month = nov,

day = "15",

doi = "10.1016/j.dam.2020.08.023",

language = "English",

volume = "303",

pages = "127--136",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "XX ",

}

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

SN - 0166-218X

VL - 303

SP - 127

EP - 136

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - XX

ER -

A note on equitable Hamiltonian cycles

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this