Back to Search
Start Over
Almost eulerian compatible spanning circuits in edge-colored graphs.
- Source :
-
Discrete Mathematics . Jan2021, Vol. 344 Issue 1, pN.PAG-N.PAG. 1p. - Publication Year :
- 2021
-
Abstract
- Let G be a (not necessarily properly) edge-colored graph. A compatible spanning circuit in G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. As two extremal cases, the existence of compatible (i.e., properly edge-colored) Hamilton cycles and compatible Euler tours have been studied extensively. More recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex v of G at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in graphs satisfying Ore-type degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times. We respectively consider graphs satisfying Fan-type degree conditions, graphs with a high edge-connectivity, and the asymptotical existence of such compatible spanning circuits in random graphs. [ABSTRACT FROM AUTHOR]
- Subjects :
- *RANDOM graphs
*GRAPH coloring
*GRAPH connectivity
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 344
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 146832139
- Full Text :
- https://doi.org/10.1016/j.disc.2020.112174