Back to Search
Start Over
Compatible spanning circuits in edge-colored graphs.
- Source :
-
Discrete Mathematics . Jul2020, Vol. 343 Issue 7, pN.PAG-N.PAG. 1p. - Publication Year :
- 2020
-
Abstract
- A spanning circuit in a graph is defined as a closed trail visiting each vertex of the graph. A compatible spanning circuit in an edge-colored graph refers to a spanning circuit in which each pair of edges traversed consecutively along the spanning circuit has distinct colors. As two extreme cases, sufficient conditions for the existence of compatible Hamilton cycles and compatible Euler tours have been obtained in previous literature. In this paper, we first establish sufficient conditions for the existence of compatible spanning circuits visiting each vertex exactly k times, for every feasible integer k , in edge-colored complete graphs and complete equipartition r -partite graphs. We also provide sufficient conditions for the existence of compatible spanning circuits visiting each vertex v at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in edge-colored graphs satisfying Ore-type degree conditions. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMPLETE graphs
*TRAVELING salesman problem
*RAMSEY numbers
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 343
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 143158901
- Full Text :
- https://doi.org/10.1016/j.disc.2020.111908