Reflecting Sequences and Universal Traversal Sequences for Graphs

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

Category
Colloquium

Speaker
H. K. Dai (CMC)

Abstract

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.

 

 

Where
Kravis Center Lower Court 62, Claremont McKenna College