On the number of congruence classes of paths

DOI10.1016/J.DISC.2011.12.017zbMATH Open1243.05113arXiv1112.4026OpenAlexW2034047164MaRDI QIDQ409484FDOQ409484

Authors: Zhicong Lin, Jiang Zeng 

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1112.4026

Recommendations

• The congruence classes of paths and cycles
• Congruence relations of paths: some combinatorial properties
• The number of path homomorphisms by the generalized Catalan number
• A note on counting homomorphisms of paths
• On congruences of paths

zbMATH Keywords

graphpathsgraph homomorphismslattice pathsgraph endomorphisms

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• Graph theory
• Title not available (Why is that?)
• An algorithm for the numbers of endomorphisms on paths (DM13208)
• The congruence classes of paths and cycles
• An algorithm for the number of path homomorphisms

Cited In (7)

• COUNTING FUNDAMENTAL PATHS IN CERTAIN GARSIDE SEMIGROUPS
• The number of path homomorphisms by the generalized Catalan number
• The congruence classes of paths and cycles
• Congruences modulo powers of 2 for the number of unique path partitions
• Graph homomorphisms between trees
• On congruences of paths
• A note on counting homomorphisms of paths

This page was built for publication: On the number of congruence classes of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409484)