Vertex deletion and cycles in multipartite tournaments
type: Item
instance of: scholarly article
title: Vertex deletion and cycles in multipartite tournaments
zbMATH Open document ID: 0939.05046
DOI: 10.1016/S0012-365X(99)90145-0
author: Meike Tewes
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2000-07-05T00:00:00Z
review text: A \(k\)-partite tournament is an orientation of a complete \(k\)-partite graph. When \(k\) is not important, we speak about a multipartite tournament. In the special case when \(k= n\), the number of vertices, we obtain a tournament, i.e. an orientation of a complete graph. It is well known and easy to show that every strong tournament \(T\) contains two vertices \(x_1\), \(x_2\) such that \(T- x_i\) is strong for \(i= 1,2\). The authors show that this result extends to general multipartite tournaments, except for one family of 2-partite tournaments and three families of 3-partite tournaments. The paper also contains some results on cycles in Hamiltonian multipartite tournaments which are not 2-strong. In particular the result that for any such digraph on \(n\geq 5\) vertices, every vertex is on a cycle of length \(n-1\) or \(n-2\).
reviewed by: Jørgen Bang-Jensen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1322053
zbMATH Keywords: strong vertex deletion
zbMATH Keywords: multipartite tournament
zbMATH Keywords: cycles
zbMATH Keywords: Hamiltonian
zbMATH Keywords: digraph
MaRDI profile type: Publication
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Quasi‐transitive digraphs
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: On multipartite tournaments
cites work: On cycles through a given vertex in multipartite tournaments
cites work: Connectivity properties of locally semicomplete digraphs
cites work: Q3220618
cites work: On Subtournaments of a Tournament
full work available at URL: s0012-365x(99)90145-0
OpenAlex ID: W4213278314
Recommended article: On cycles through a given vertex in multipartite tournaments
Recommended article: Vertex-disjoint cycles in bipartite tournaments
Recommended article: Vertex-disjoint cycles in regular tournaments
Recommended article: Q4545818
Recommended article: Cycles through \(k\) vertices in bipartite tournaments
Recommended article: On cycles in multipartite tournaments
Recommended article: Vertex-disjoint cycles of different lengths in multipartite tournaments
Recommended article: Q5702650
Recommended article: Cycles in multipartite tournaments: Results and problems
description: scientific article; zbMATH DE number 1322053