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)

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Tijdschrift	Discrete Applied Mathematics
Volume	XX
Nummer van het tijdschrift	XX
DOI's	https://doi.org/10.1016/j.dam.2020.08.023
Status	E-publicatie vóór gedrukte publicatie - 29 aug 2020

Toegang tot document

10.1016/j.dam.2020.08.023

Link to publication in Scopus

Vingerafdruk Duik in de onderzoeksthema's van 'A note on equitable Hamiltonian cycles'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@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 = "2020",

month = aug,

day = "29",

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

language = "English",

volume = "XX",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

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 - 2020/8/29

Y1 - 2020/8/29

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 - XX

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - XX

ER -