Subdivisions of transitive tournaments (Q1590220): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3852212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extremal Graphs without Large Forbidden Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Highly linked graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extremal digraph results for topological complete subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topological cliques in graphs II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen / rank | |||
Normal rank |
Latest revision as of 11:22, 3 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subdivisions of transitive tournaments |
scientific article |
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