Subdivisions of Transitive Tournaments |
| |
Authors: | A D Scott |
| |
Institution: | Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, U.K. |
| |
Abstract: | We prove that, for r ≥ 2 andn ≥ n(r), every directed graph with n vertices and more edges than the r -partite Turán graph T(r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations ofT (r, n) induced by orderings of the vertex classes. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|