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$ 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$

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.