About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Lower bounds on the length of universal traversal sequences
Abstract
Universal traversal sequences for d-regular n-vertex graphs require length Ω(d2n2 + dn2 log( n d)), for 3 ≤d≤ n 3 - 2. This is nearly tight for d = Θ(n). We also introduce and study several variations on the problem, e.g., edge-universal traversal sequences, showing how improved lower bounds on these would improve the bounds given above. © 1992.