Cantor--Bernstein type theorem for locally constrained graph homomorphisms (Q852701)

From MaRDI portal
scientific article
In more languages
Configure
Language Label Description Also known as
English
Cantor--Bernstein type theorem for locally constrained graph homomorphisms
scientific article

    Statements

    Cantor--Bernstein type theorem for locally constrained graph homomorphisms (English)
    15 November 2006
    The graphs considered in this paper are understood to be undirected and without loops or multiple edges. For graphs \(G\) and \(H\), a mapping \(f:V(G) \rightarrow V(H)\) is called a homomorphism if adjacent vertices of \(G\) are mapped onto adjacent vertices of \(H\). A homomorphism \(f:V(G) \rightarrow V(H)\) is locally injective if, for every \(u \in V(G)\), the neighbors of \(u\) are mapped injectively in the set of neighbors of \(f(u)\); analogously, the terms locally surjective and locally bijective are defined. The main result of the paper is the following theorem which is motivated by the Cantor-Bernstein theorem. For a graph \(G\) (finite or infinite) and a finite connected graph \(H\), suppose that there is a locally surjective homomorphism \(g:G \rightarrow H\) and a locally injective homomorphism \(h:G \rightarrow H\). Then \(g\) and \(h\) are locally bijective. This generalizes and unifies previous results of \textit{P.~Kristiansen} and \textit{J. A.~Telle} [Lect. Notes Comput. Sci. 1969, 456--466 (2000; Zbl 1044.68129)] and \textit{J.~Fiala} and \textit{J.~Kratochvíl} [Discuss. Math., Graph Theory 22, 89--99 (2002; Zbl 1017.05094)].
    locally injective
    locally surjective
    locally bijective