Subdivisions of transitive tournaments
type: Item
instance of: scholarly article
title: Subdivisions of transitive tournaments
zbMATH Open document ID: 0965.05049
published in: European Journal of Combinatorics
publication date: 2001-08-02T00:00:00Z
review text: A subdivision of a digraph is a digraph obtained by replacing arcs by directed paths (in the same direction as the arcs). It is proved that, for \(r\geq 2\) and \(n\geq n(r)\), every digraph with \(n\) vertices and more arcs than the \(r\)-partite Turán graph \(T(r,n)\), contains a subdivision of the transitive tournament on \(r+1\) vertices. Moreover, the extremal digraphs are the orientations of \(T(r,n)\) induced by orderings of the vertex classes.
reviewed by: G. Gutin
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1545628
zbMATH Keywords: subdivision
zbMATH Keywords: Turán graph
zbMATH Keywords: transitive tournament
zbMATH Keywords: extremal digraphs
author: Alex Scott
MaRDI profile type: Publication
full work available at URL: eujc.2000.0406
OpenAlex ID: W2169373695
cites work: Q3852212
cites work: Extremal Graphs without Large Forbidden Subgraphs
cites work: Highly linked graphs
cites work: Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
cites work: Extremal digraph results for topological complete subgraphs
cites work: Topological cliques in graphs II
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
DOI: 10.1006/EUJC.2000.0406
description: scientific article; zbMATH DE number 1545628