A well-quasi-order for tournaments

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

A digraph H is immersed in a digraph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. For graphs the same relation (using paths instead of directed paths) is a well-quasi-order; that is, in every infinite set of graphs some one of them is immersed in some other. The same is not true for digraphs in general; but we show it is true for tournaments (a tournament is a directed complete graph).

Original languageEnglish (US)
Pages (from-to)47-53
Number of pages7
JournalJournal of Combinatorial Theory. Series B
Volume101
Issue number1
DOIs
StatePublished - Jan 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Digraph
  • Immersion
  • Minor
  • Tournament
  • Well-quasi-order

Fingerprint

Dive into the research topics of 'A well-quasi-order for tournaments'. Together they form a unique fingerprint.

Cite this