On the capacity of digraphs

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

For a digraph G = (V, E) let w(Gn) denote the maximum possible cardinality of a subset S of Vn in which for every ordered pair (u1, u2, . . . , un) and (v1, v2, . . . , vn) of members of S there is some 1 ≤ i ≤ n such that (ui, vi) ∈ E. The capacity C(G) of G is C(G) = limn→∞[(w(Gn))1/n]. It is shown that for any digraph G with maximum outdegree d, C(G) ≤ d + 1. It is also shown that for every n there is a tournament T on 2n vertices whose capacity is at least √n, whereas the maximum number of vertices in a transitive subtournament in it is only O(log n). This settles a question of Körner and Simonyi.

Original languageEnglish (US)
Pages (from-to)1-5
Number of pages5
JournalEuropean Journal of Combinatorics
Volume19
Issue number1
DOIs
StatePublished - Jan 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the capacity of digraphs'. Together they form a unique fingerprint.

  • Cite this