  We formulate three current models of discrete-time quantum walks in a
combinatorial way. These walks are shown to be closely related to rotation
systems and 1-factorizations of graphs. For two of the models, we compute the
traces and total entropies of the average mixing matrices for some cubic
graphs. The trace captures how likely a quantum walk is to revisit the state it
started with, and the total entropy measures how close the limiting
distribution is to uniform. Our numerical results indicate three relations
between quantum walks and graph structures: for the first model, rotation
systems with higher genera give lower traces and higher entropies, and for the
second model, the symmetric 1-factorizations always give the highest trace.
