On the number of congruence classes of paths (Q409484)

A homomorphism between graphs is a function so that, if two vertices are adjacent in the domain, then their images are adjacent, too. As a lemma for their main result, the authors prove a new formula for the number of graph homomorphisms from a path with \(n\) vertices to a path with \(k\) vertices. A graph endomorphism is a graph homomorphism from a graph to itself. The congruence class induced by an endomorphism is the partition of the graph in which elements with the same image are in the same block. Let \(l_k (n)\) be the number of \(n-k+1\)-element congruence classes of a path with \(n\) vertices. The authors prove a formula for \(l_k (n)\) when \(n\geq 2k\), thereby answering a question from the article [\textit{M. A. Michels} and \textit{U. Knauer}, ``The congruence classes of paths and cycles,'' Discrete Math. 309, No.\,17, 5352--5359 (2009; Zbl 1231.05149)].