Reflecting Sequences and Universal Traversal Sequences for Graphs

Start: 11/02/2016 - 4:15pm
End  : 11/02/2016 - 5:15pm


H. K. Dai (CMC)


Graph traversal is of fundamental importance to computing.  The study of universal traversal sequences and reflecting sequences is motivated by the complexity of graph traversal.  A universal traversal sequence for the family of all connected d-regular graphs with an edge-labeling is a sequence of symbols 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.  This presentation introduces the combinatorial nature of universal traversal sequences and reflecting sequences and their length lower-bound arguments.



Kravis Center Lower Court 62, Claremont McKenna College

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences