Abstract
Let Θ(n,k) be the set of digraphs of order n that have at most one walk of length k with the same endpoints. Let θ(n,k) be the maximum number of arcs of a digraph in Θ(n,k). We prove that if n<5 and k<n-1 then θ(n,k)=n(n-1)2 and this maximum number is attained at D if and only if D is a transitive tournament. θ(n,n-2) and θ(n,n-3) are also determined.
| Original language | English |
|---|---|
| Pages (from-to) | 70-79 |
| Number of pages | 10 |
| Journal | Discrete Mathematics |
| Volume | 311 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2011 |
Keywords
- Digraph
- Number of arcs
- Tournament
- Walk