Compatible spanning circuits in edge-colored graphs

Zhiwei Guo

Research output: ThesisPhD Thesis - Research external, graduation UT

1 Citation (Scopus)
21 Downloads (Pure)

Abstract

A spanning circuit in a graph is a closed trail (no edge is traversed more than once) visiting (containing) each vertex of the graph. A Hamilton cycle of a graph refers to a spanning circuit that visits each vertex of the graph exactly once, and an Euler tour of a graph refers to a spanning circuit that traverses each edge of the graph. Spanning circuits are common generalizations of Hamilton cycles and Euler tours, two popular and well-studied concepts within graph theory. A compatible spanning circuit in a (not necessarily properly) edge-colored graph is a spanning circuit in which any two consecutively traversed edges have distinct colors.

Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours) in specific edge-colored graphs, and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature.

In this thesis, we mainly concentrate our efforts on the existence of compatible spanning circuits visiting each vertex exactly (or at least) a specified number of times in specific edge-colored graphs, from both a sufficient condition perspective and an algorithmic perspective. In addition, we also consider similar problems in (di)graphs for which certain generalizations of (arc-) edge-colorings have been defined. In presenting our results, we restate some interesting related problems and conjectures that remain unresolved, as well as we also present several new open problems. We hope that these problems and conjectures attract more attention from other researchers.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Faculty of Electrical Engineering, Mathematics and Computer Science
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Li, Xueliang, Supervisor
  • Zhang, Shenggui, Co-Supervisor
Thesis sponsors
Award date17 Sep 2020
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-5046-8
Electronic ISBNs978-90-365-5046-8
DOIs
Publication statusPublished - 17 Sep 2020

Keywords

  • Edge-colored graph
  • Compatible spanning circuit
  • Supereulerian graph
  • NP-complete problem
  • Polynomial-time algorithm

Fingerprint Dive into the research topics of 'Compatible spanning circuits in edge-colored graphs'. Together they form a unique fingerprint.

  • Cite this