Subdivisions of transitive tournaments (Q1590220)
From MaRDI portal
!
WARNING
This is the item page for this Wikibase entity, intended for internal use and editing purposes.
Please use the normal view instead:
scientific article; zbMATH DE number 1545628
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Subdivisions of transitive tournaments |
scientific article; zbMATH DE number 1545628 |
Statements
Subdivisions of transitive tournaments (English)
0 references
2 August 2001
0 references
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.
0 references
subdivision
0 references
Turán graph
0 references
transitive tournament
0 references
extremal digraphs
0 references
0.8863723874092102
0 references
0.8430539965629578
0 references
0.8419482111930847
0 references
0.833267867565155
0 references
0.8321360349655151
0 references
