Almost all almost regular c-partite tournaments with c ≥ 5 are vertex pancyclic

Meike Tewes, Lutz Volkmann, Anders Yeo

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)

Abstract

A tournament is an orientation of a complete graph and a multipartite or c-partite tournament is an orientation of a complete c-partite graph. If D is a digraph, then let d+(x) be the outdegree and d-(x) the indegree of the vertex x in D. The minimum (maximum) outdegree and the minimum (maximum) indegree of D are denoted by δ++) and δ--), respectively. In addition, we define δ = min(δ+-) and Δ =max(Δ+-). A digraph is regular when δ = Δ and almost regular when Δ - δ 1. Recently, the third author proved that all regular c-partite tournaments are vertex pancyclic when c ≥ 5, and that all, except possibly a finite number, regular 4-partite tournaments are vertex pancyclic. Clearly, in a regular multipartite tournament, each partite set has the same cardinality. As a supplement of Yeo's result we prove first that an almost regular c-partite tournament with c ≥ 5 is vertex pancyclic, if all partite sets have the same cardinality. Second, we show that all almost regular c-partite tournaments are vertex pancyclic when c ≥ 8, and third that all, except possibly a finite number, almost regular c-partite tournaments are vertex pancyclic when c ≥ 5.

Original languageEnglish
Pages (from-to)201-228
Number of pages28
JournalDiscrete Mathematics
Volume242
Issue number1-3
DOIs
Publication statusPublished - 1 Jun 2002
Externally publishedYes

Keywords

  • Cycles
  • Multipartite tournaments
  • Pancycliciry

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Almost all almost regular c-partite tournaments with c ≥ 5 are vertex pancyclic'. Together they form a unique fingerprint.

Cite this