Compatible spanning circuits in edge-colored Fan-type graphs

Zhiwei Guo, Hajo Broersma, Binlong Li, Shenggui Zhang

Research output: Contribution to conferencePaperAcademicpeer-review

Abstract

A spanning circuit in a graph G is defined as a closed trail visiting each vertex of G. 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 have distinct colors. As two extreme cases, the existence of compatible Hamilton cycles and compatible Eulerian circuits in edge-colored graphs has been studied extensively. In recent results the existence of compatible spanning circuits visiting each vertex v at least b(d(v)-1)/2c times in edge-colored graphs satisfying Ore-type conditions has been proved. In this presentation, we show several results on the existence of compatible spanning circuits visiting each vertex at least a specified number of times in edge-colored Fan-type graphs. We will also present a sufficient condition for the existence of such compatible spanning circuits in edge-colored 2(k + 1)-edge-connected graphs, as well as some sufficient conditions for the asymptotical existence of compatible spanning circuits in edge-colored random graphs.

Original languageEnglish
Pages61-64
Number of pages4
Publication statusPublished - 1 Jan 2019
Event17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - U-Parkhotel, Enschede, Netherlands
Duration: 1 Jul 20193 Jul 2019
Conference number: 17
http://wwwhome.math.utwente.nl/~ctw/

Workshop

Workshop17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019
Abbreviated titleCTW 2019
CountryNetherlands
CityEnschede
Period1/07/193/07/19
Internet address

Fingerprint Dive into the research topics of 'Compatible spanning circuits in edge-colored Fan-type graphs'. Together they form a unique fingerprint.

Cite this