Abstract
An n-labeled complete digraph G is a complete digraph with n+1 vertices and n(n+1) edges labeled {1,2,...,n}* such that there is a unique edge of each label emanating from each vertex. A sequence S in {1,2,...,n}*: and a starting vertex of G define a unique walk in G, in the obvious way. Suppose S is a sequence such that for each such G and each starting point in it, the corresponding walk contains all the vertices of G. We show that the length of S is at least Ω(n2), improving a previously known Ω(nlog2n/log logn) lower bound of Bar-Noy, Borodin, Karchmer, Linial and Werman.
Original language | English (US) |
---|---|
Pages (from-to) | 25-28 |
Number of pages | 4 |
Journal | Discrete Applied Mathematics |
Volume | 27 |
Issue number | 1-2 |
DOIs | |
State | Published - May 1990 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics