𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Capacity of Digraphs

✍ Scribed by Noga Alon

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
76 KB
Volume
19
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

For a digraph G = (V, E) let w(G n ) denote the maximum possible cardinality of a subset S of V n in which for every ordered pair

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.

πŸ“œ SIMILAR VOLUMES

On the number of quasi-kernels in digrap
On the number of quasi-kernels in digraphs
✍ Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 89 KB

## Abstract A vertex set __X__ of a digraph __D__ = (__V, A__) is a __kernel__ if __X__ is independent (i.e., all pairs of distinct vertices of __X__ are non‐adjacent) and for every __v__ ∈ __V__‐__X__ there exists __x__ ∈ __X__ such that __vx__ ∈ __A__. A vertex set __X__ of a digraph __D__ = (__V

On independent circuits of a digraph
On independent circuits of a digraph
✍ S. Rao Kosaraju πŸ“‚ Article πŸ“… 1977 πŸ› John Wiley and Sons 🌐 English βš– 156 KB

## Abstract If every three circuits of a digraph have a common vertex, then all the circuits have one.

On digraphs with the odd cycle property
On digraphs with the odd cycle property
✍ Rachel Manber; Jia-Yu Shao πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 462 KB

We say that a digraph D has the odd cycle property if there exists an edge subset S such that every cycle of D has an odd number of edges from S. We give necessary and sufficient conditions for a digraph to have the odd cycle property. We also consider the analogous problem for graphs.

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; FοΏ½brega, J. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

It has been proved that if the diameter D of a digraph G satisfies D Υ… 2ᐉ Οͺ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Υ… 2ᐉ Οͺ 1, then G is edge-superconnected. In this paper, we studied some similar condi

On the connectivity and the conditional
On the connectivity and the conditional diameter of graphs and digraphs
✍ Balbuena, C.; Carmona, A.; FοΏ½brega, J.; Fiol, M. A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .