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. At-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 Omega(n(1.51)) and Omega(d(0.49)n(2.51)) for universal traversal sequences for 2- and d-regular graphs, respectively, of n vertices, where 3 <= d <= n/17 + 1. (C) 2015 Elsevier B.V. All rights reserved.