Formulas for the Number of Weak Homomorphisms from Paths to Rectangular Grid Graphs

A weak homomorphism from graph G to graph H is a mapping f:V(G)→V(H), where either f(x)=f(y) or {f(x),f(y)}∈E(H) hold for all {x,y}∈E(G). A rectangular grid graph is formed by taking the Cartesian product of two paths. Counting weak homomorphisms is a fundamental problem in graph theory. In this paper, we present formulas for calculating the number of weak homomorphisms from paths to rectangular grid graphs. This count directly corresponds to the number of partial walks with length m within the rectangular grid graph, offering a combinatorial solution to this enumeration problem.