Universal sequences for complete graphs

N. Alon, Y. Azar, Y. Ravid

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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 languageEnglish (US)
Pages (from-to)25-28
Number of pages4
JournalDiscrete Applied Mathematics
Volume27
Issue number1-2
DOIs
StatePublished - May 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Universal sequences for complete graphs'. Together they form a unique fingerprint.

Cite this