An algorithm for the number of path homomorphisms

被引：8

作者：

Arworn, Srichan ^{[2
]}

Wojtylak, Piotr ^{[1
]}

机构：

[1] Silesian Univ, Inst Math, PL-40007 Katowice, Poland

[2] Chiang Mai Univ, Dept Math, Fac Sci, Chiang Mai 50200, Thailand

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 18期

关键词：

Graph; Undirected path; Graph homomorphism; ENDOMORPHISM SPECTRA; GRAPHS;

D O I：

10.1016/j.disc.2008.04.010

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A homomorphism of a graph G(1) = (V-1, E-1) to a graph G(2) = (V-2, E-2) is a mapping from the vertex set V-1 of G(1) to the vertex set V-2 of G(2) which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：5569 / 5573

页数：5

共 6 条

[1] ARWORN, DISCRETE MA IN PRESS, DOI DOI 10.1016/J.DISC.2007.12.049
[2] ENDOMORPHISM SPECTRA OF GRAPHS
BOTTCHER, M
KNAUER, U
[J]. DISCRETE MATHEMATICS, 1992, 109 (1-3) : 45 - 57
[3] Postscript:: "Endomorphism spectra of graphs" [Discrete Mathematics 109 (1992) 45-57]
Böttcher, M
Knauer, U
[J]. DISCRETE MATHEMATICS, 2003, 270 (1-3) : 329 - 331
[4] Hell Pavol, 2004, Graphs and Homomorphisms, V28, pxii+244
[5] KNAUER U, 1992, WORDS, LANGUAGES AND COMBINATORICS, P273
[6] MICHELS M, 2005, THESIS C VONOSSIETZK

← 1 →