Modularity of cycles and paths in graphs

Certain problems related to the length of cycles and paths modulo a given integer are studied. Linear-time algorithms are presented that determine whether all cycles in an undirected graph are of length P mod Q and whether all paths between two specified nodes are of length P mod Q , for fixed integers P . Q . These results are compared to those for directed graphs.