Length lower bounds for reflecting sequences and universal traversal sequences

A universal traversal sequence for the family of all connected d-regular graphs of order n with an edge-labeling is a sequence of {0,1,…,d−1}∗ that traverses every graph of the family starting at every vertex of the graph. Reflecting sequences are variants of universal traversal sequences. A t-reflecting sequence for the family of all labeled chains of length n is a sequence of {0,1}∗ that alternately visits the end-vertices and reflects at least t times in every labeled chain of the family. We present an algorithm for finding lower bounds on the lengths of reflecting sequences for labeled chains. Using the algorithm, we show a length lower bound of 19t−214 for t-reflecting sequences for labeled chains of length 7, which yields the length lower bounds of Ω(n1.51) and Ω(d0.49n2.51) for universal traversal sequences for 2- and d-regular graphs, respectively, of n vertices, where 3≤d≤n17+1.