A Note on the Cycle Structure of Cartesian-Product Graphs.
07 October 1987
We derive a tight lower bound on the number of classes in a particular equivalence relation on the edges of a cartesian- product graph. This bound is significant, because it appears in the worst-case running time of a fairly straightforward cartesian-factoring algorithm.