Universal traversal sequences for expander graphs (Q1802060)

We give an explicit construction of a polynomial length universal sequence for a class of constant degree expander graphs. The extra requirements is that the labeling of the edges be consistent, i.e. that for each vertex not only the outgoing labels be distinct, but the incoming labels as well. Consistent labeling is an intermediate requirement between the weaker unrestricted labeling and the stronge requirement of symmetric labeling (where both labels on each edge are identical). For any of them, obtaining universal traversal sequences in uniform logspace will put undirected reachability in DSPACE\((\log n)\). For expanders we do not know how to handle unrestricted labeling, while the symmetric case is trivial (since the diameter is small). Here we handle the intermediate case of consistent labeling. Our construction is based on ideas from the universal sequence for cliques constructed in [\textit{H. J. Karloff, R. Paturi} and \textit{J. Simon}, Universal traversal sequences of length \(n^{O(\log n))}\) for cliques, Inform. Process. Lett. 28, 241-243 (1988; Zbl 0667.68078)].