Title

A Generalization Of Turán's Theorem To Directed Graphs

Document Type

Article

Publication Date

1980

Published In

Discrete Mathematics

Abstract

We consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on mvertices. For an integer n⩾2, let Tn denote the transitive tournament with vertex set Xn={1,2,3,…,n} and edge set {(i,j):1⩽i