# zbMATH — the first resource for mathematics

On the capacity of digraphs. (English) Zbl 0894.05031
For a digraph $$G= (V,E)$$ let $$\omega(G^n)$$ denote the maximum possible cardinality of a subset $$S$$ of $$V^n$$ in which for every ordered pair of $$n$$-tuples $$(u_1, u_2,\dots, u_n)$$ and $$(v_1, v_2,\dots, v_n)$$ of members of $$S$$ there is some $$i$$ with $$1\leq i\leq n$$ such that $$(u_i,v_i)\in E$$. The capacity $$C(G)$$ of $$G$$ is $$C(G)= \lim_{n\to\infty} [(\omega(G^n))^{1/n}]$$. It is shown that if $$G$$ has maximum outdegree $$d$$, then $$C(G)\leq d+1$$. It is also shown that for every $$n$$ there is a tournament $$T$$ on $$2n$$ vertices whose capacity is at least $$\sqrt{n}$$, whereas the maximum number of vertices in a transitive subtournament of $$T$$ is only $$O(\log n)$$. This disproves a conjecture of Körner and Simonyi.

##### MSC:
 05C35 Extremal problems in graph theory 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
digraph; capacity; tournament
Full Text: