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 wellstudied concepts within graph theory. A compatible spanning circuit in a (not necessarily properly) edgecolored 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 edgecolored graphs, and polynomialtime 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 edgecolored 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) edgecolorings 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.
Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours) in specific edgecolored graphs, and polynomialtime 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 edgecolored 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) edgecolorings 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 language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  17 Sep 2020 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036550468 
Electronic ISBNs  9789036550468 
DOIs  
Publication status  Published  17 Sep 2020 
Keywords
 Edgecolored graph
 Compatible spanning circuit
 Supereulerian graph
 NPcomplete problem
 Polynomialtime algorithm
Fingerprint Dive into the research topics of 'Compatible spanning circuits in edgecolored graphs'. Together they form a unique fingerprint.
Cite this
Guo, Z. (2020). Compatible spanning circuits in edgecolored graphs. Enschede: University of Twente. https://doi.org/10.3990/1.9789036550468