On the number of congruence classes of paths

Abstract

Let $P_n$ denote the undirected path of length $n-1$. The cardinality of the set of congruence classes induced by the graph homomorphisms from $P_n$ onto $P_k$ is determined. This settles an open problem of Michels and Knauer (Disc. Math., 309\ (2009)\ 5352-5359). Our result is based on a new proven formula of the number of homomorphisms between paths.

arXiv comment11 pages, 2 figures, to appear in Discrete Mathematics