-1
$\begingroup$

A simple, undirected graph $G=(V,E)$ is said to be vertex-transitive if for all $a,b\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(a) = b$.

If $G = (\omega, E)$ is vertex-transitive and connected, is there a bijection $p:\mathbb{Z}\to \omega$ such that $\{p(k), p(k+1)\} \in E$ for all $k\in\mathbb{Z}$?

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ If $G$ is a regular tree of degree $d \geq 3$, there's clearly no such $p$, unless I'm missing something. $\endgroup$
    – Ilkka Törmä
    Commented Mar 7, 2022 at 11:06
  • 2
    $\begingroup$ By "bijection" did you mean "injection"? In plain language, are you just asking if $G$ contains a two-way infinite path? $\endgroup$
    – bof
    Commented Mar 7, 2022 at 23:24
  • 1
    $\begingroup$ @bof Thanks for your question for clarification. I am asking whether there is a two-way infinite path covering all vertices - hence bijection $\endgroup$
    – Dominic van der Zypen
    Commented Mar 8, 2022 at 9:56
  • 4
    $\begingroup$ But if there's such a trivial counterexample, the question is off-topic here. $\endgroup$
    – YCor
    Commented Mar 8, 2022 at 12:07
  • 2
    $\begingroup$ With "injection" instead of "bijection" there's an easy affirmative answer. Namely, a graph contains a $\mathbb Z$-path (not necessarily Hamiltonian) if either (1) every vertex has infinite degree, or (2) every vertex has finite degree, and some vertex $v$ is the midpoint of a path of length $2n$ for every $n\in\mathbb N$. $\endgroup$
    – bof
    Commented Mar 9, 2022 at 0:23

1 Answer 1

Reset to default
2
$\begingroup$

If $G$ is a regular tree of degree $d \geq 3$, there's clearly no such $p$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .