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$
2
  • $\begingroup$ Do you mean: a map which is injective neighborhood but not bijective?. $\endgroup$
    – Wlod AA
    May 28, 2018 at 8:02
  • $\begingroup$ @WlodAA Correct $\endgroup$ May 28, 2018 at 8:28

2 Answers 2

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$
4
  • $\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$ May 28, 2018 at 8:28
  • $\begingroup$ Ah, good point, sorry! Yes, is G countable? $\endgroup$
    – Adam
    May 28, 2018 at 8:32
  • $\begingroup$ My question is just whether there is an infinite (countable or uncountable) graph with this property $\endgroup$ May 28, 2018 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, 2018 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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