  Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper
investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a
closed walk which visits every vertex an odd number of times, where we remark
that the walk may use an edge more than once. First, we give a complete
characterization of the graphs which have PHCs, and give a linear time
algorithm to find a PHC, in which every edge appears at most four times, in
fact. In contrast, we show that finding a PHC is NP-hard if a closed walk is
allowed to use each edge at most z times for each z=1,2,3 (PHCz for short),
even when a given graph is two-edge connected. We then further investigate the
PHC3 problem, and show that the problem is in P when an input graph is
four-edge connected. Finally, we are concerned with three (or two)-edge
connected graphs, and show that the PHC3 is in P for any C_>=5-free or P6-free
graphs. Note that the Hamiltonian cycle problem is known to be NP-hard for
those graph classes.
