2
$\begingroup$

The concept of neighborhood maps was looked at in a previous question.

Let $G= (V,E)$ be a simple, undirected graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\} \in E\}$. Note that we always have $v\notin N(v)$. A function $f:V\to V$ is said to be a neighborhood map if $f(v)\in N(v)$ for all $v\in V$.

Does there exist a graph $G=(V,E)$ that admits an injective neighborhood map, but not a bijective one?

(Clearly, if such a graph exists, it is necessarily infinite.)

$\endgroup$
  • $\begingroup$ Do you mean: a map which is injective neighborhood but not bijective?. $\endgroup$ – Wlod AA May 28 '18 at 8:02
  • $\begingroup$ @WlodAA Correct $\endgroup$ – Dominic van der Zypen May 28 '18 at 8:28
5
$\begingroup$

The answer is no. If $f:V \to V$ is an injective map, it is a disjoint union of finite cycles, copies of the successor function in $\mathbb{Z}$ and copies of the successor function in $\mathbb{N}$. Leave the first two kinds alone and replace all of the third kind by (the appropiate copy of) the function that swaps each even natural number with its successor. We now obtain a bijection and if the original function $f$ was a neighborhood map, the new one is also a neighborhood map. Note that the cardinality of $V$ is not relevant.

$\endgroup$
2
$\begingroup$

Not for finite graphs: a neighborhood map takes $V$ to itself, so injective implies bijective.

$\endgroup$
  • $\begingroup$ That's right, the graph must be infinite. That is the reason I included the "infinite-combinatorics" tag. Maybe I should write the remark about infinity in the question? $\endgroup$ – Dominic van der Zypen May 28 '18 at 8:28
  • $\begingroup$ Ah, good point, sorry! Yes, is G countable? $\endgroup$ – Adam May 28 '18 at 8:32
  • $\begingroup$ My question is just whether there is an infinite (countable or uncountable) graph with this property $\endgroup$ – Dominic van der Zypen May 28 '18 at 8:33
  • $\begingroup$ You had earlier a trivial but correct answer (the question was trivial). But now you have edited your earlier version, hence now I'd cancel this up-vote (if I knew how). $\endgroup$ – Wlod AA May 28 '18 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.