An Algorithm for the Numbers of Homomorphisms from Paths to Rectangular Grid Graphs

Hatairat Yingtaweesittikul, Sayan Panma and Penying Rochanakul ()
Additional contact information
Hatairat Yingtaweesittikul: Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand
Sayan Panma: Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand
Penying Rochanakul: Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand

Mathematics, 2023, vol. 11, issue 11, 1-14

Abstract: Let G and H be graphs. A mapping f from the vertices of G to the vertices of H is known as a h o m o m o r p h i s m from G to H if, for every pair of adjacent vertices x and y in G , the vertices f ( x ) and f ( y ) are adjacent in H . A rectangular grid graph is the Cartesian product of two path graphs. In this paper, we provide a formula to determine the number of homomorphisms from paths to rectangular grid graphs. This formula gives the solution to the problem concerning the number of walks in the rectangular grid graphs.

Keywords: homomorphisms; graph homomorphisms; path graphs; rectangular grid graphs; grid graphs (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/11/2587/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/11/2587/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:11:p:2587-:d:1164447

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().