Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647918 | Discrete Mathematics | 2012 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zhicong Lin, Jiang Zeng,