On the number of congruence classes of paths

Let PnPn denote the undirected path of length n−1n−1. The cardinality of the set of congruence classes induced by the graph homomorphisms from PnPn onto PkPk is determined. This settles an open problem of Michels and Knauer [M. A. Michels, U. Knauer, The congruence classes of paths and cycles, Discrete Mathematics, 309 (2009) 5352–5359]. Our result is based on a new proven formula of the number of homomorphisms between paths.