4
$\begingroup$

If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path.

Is there a graph $G$ with $V(G) = \omega$ and the following properties?

  1. There is no surjective $\mathbb{Z}$- or $\omega$-path on $G$;
  2. For every vertex $v\in V(G) = \omega$, there is a surjective $\mathbb{Z}$- or $\omega$-path on $G\setminus \{v\}$.
$\endgroup$
1
  • $\begingroup$ For clarity, I would write "surjective (on V)", so that people don't think of covering all edges. $\endgroup$ Commented Feb 20, 2015 at 16:20

1 Answer 1

10
$\begingroup$

Yes, Figure 2 of Carsten Thomassen's paper "Planar and infinite hypohamiltonian and hypotraceable graphs" (doi:10.1016/0012-365X(76)90071-6) presents a graph that does not have a 2-way infinite hamiltonian path, but such that every vertex-deleted subgraph does have such a hamiltonian path. Since the graph has 2 ends, it also does not have a 1-way infinite hamiltonian path. (Your surjective ω-paths and surjective ℤ-paths are called 1-way infinite hamiltonian paths and 2-way infinite hamiltonian paths by Thomassen.)

$\endgroup$

You must log in to answer this question.

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