Universal sequences and graph cover times A short survey

Let G be a d-regular graph on n vertices. At each vertex v, let the edges incident with v be given the distinct labels 1,…,d. The labels at the two ends of an edge are not necessarily equal, that is, each edge is labeled twice. A sequence σ in {1,…, d}* is said to traverseG from v if, by starting from v and following the sequence of edge labels σ, one covers all the vertices of G. Let G _n,d be a collection of d-regular graphs. A sequence σ is called universal for G _n,d if it traverses every graph in G _n,d , from every starting point v. For a given family G _n,d , the length of the shortest universal sequence for G _n,d is denoted U(G _n,d )