Some algorithmic results for finding compatible spanning circuits in edge-colored graphs
- PDF / 364,639 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 192 Views
Some algorithmic results for finding compatible spanning circuits in edge-colored graphs Zhiwei Guo1,2 · Hajo Broersma2
· Ruonan Li1,3 · Shenggui Zhang1,3
© The Author(s) 2020
Abstract A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G 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), and polynomialtime algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erd˝os from the 1970s. Keywords Edge-colored graph · Compatible spanning circuit · NP-complete problem · Polynomial-time algorithm Mathematics Subject Classification 05C15 · 05C38 · 05C45 · 05C85
Supported by NSFC (Nos. 11671320 and U1803263), CSC (No. 201806290049) and the Fundamental Research Funds for the Central Universities (Nos. 31020180QD124 and 3102019ghjd003).
B
Hajo Broersma [email protected]
1
School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an 710129, Shaanxi, People’s Republic of China
2
Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
3
Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an 710129, Shaanxi, People’s Republic of China
123
Journal of Combinatorial Optimization
1 Introduction In this paper we consider only finite undirected simple graphs. For terminology and notations not defined here, we refer the reader to the textbook of Bondy and Murty (2008). Let G be a graph. We use V (G) and E(G) to denote the vertex set and edge set of G, respectively. For a vertex v of G, we denote by E G (v) the set of edges of G incident with v, and we denote by N G (v) the set of neighbors of v in G. The degree of a vertex v in a graph G, denoted by dG (v), is defined to be the cardinality of E G (v). We write (G) = max{dG (v) | v ∈ V (G)}. If no ambiguity can arise, we will denote E G (v), N G (v) and dG (v) by E(v), N (v) and d(v), respectively. A spanning circuit in a graph G is defined as a closed trail that visits (contains) each vertex of G. A Hamilton cycle of G refers to a spanning circuit visiting each vertex of G exactly once; an Euler tour of G refers to a span
Data Loading...
