On the number of congruence classes of paths

被引：6

作者：

Lin, Zhicong ^{[2
]}

Zeng, Jiang ^{[1
]}

机构：

[1] Univ Lyon 1, Univ Lyon, Inst Camille Jordan, CNRS,UMR 5208, F-69622 Villeurbanne, France

[2] Lanzhou Univ, Dept Math & Stat, Lanzhou 730000, Peoples R China

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 06期

关键词：

Graph; Graph endomorphisms; Graph homomorphisms; Paths; Lattice paths;

D O I：

10.1016/j.disc.2011.12.017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 [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. (C) 2011 Elsevier BM. All rights reserved.

引用

页码：1300 / 1307

页数：8