On the number of congruence classes of paths

DOI10.1016/J.DISC.2011.12.017MaRDI QIDQ409484zbMATHOpenAlexFDO

Authors Zhicong Lin, Jiang Zeng

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3681764 (Why is no real title available?)
• An algorithm for the number of path homomorphisms
• An algorithm for the numbers of endomorphisms on paths (DM13208)
• Graph theory
• The congruence classes of paths and cycles

Cited in

(9)

• On congruences of paths
• Graph homomorphisms between trees
• The number of path homomorphisms by the generalized Catalan number
• The congruence classes of paths and cycles
• COUNTING FUNDAMENTAL PATHS IN CERTAIN GARSIDE SEMIGROUPS
• Congruence relations of paths: some combinatorial properties
• A note on counting homomorphisms of paths
• The number of graph homomorphisms between paths and cycles with loops, a problem from Stanley's enumerative combinatorics
• Congruences modulo powers of 2 for the number of unique path partitions

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)