Almost eulerian compatible spanning circuits in edge-colored graphs

Zhiwei Guo, Hajo Broersma*, Binlong Li, Shenggui Zhang

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
5 Downloads (Pure)

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.

Original languageEnglish
Article number112174
JournalDiscrete mathematics
Volume344
Issue number1
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Compatible spanning circuit
  • Edge-colored graph
  • Fan-type degree condition
  • Random graph
  • Supereulerian graph
  • UT-Hybrid-D

Fingerprint

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

Cite this