1
$\begingroup$

If $\omega$ denotes the set of the natural numbers (= the first infinite ordinal), and if $E\subseteq\binom{\omega}{2}$ is any subset, we call a map $f\colon\omega\to\omega$ a walk in the graph $(\omega,E)$ if and only if $\{f(k),f(k+1)\}\in E$ for all $k\in\omega$.

We call $f$ a walk a Hamiltonian walk1 if and only if it is surjective.

Question.

Is there $E \subseteq \binom{\omega}{2}$ such that

  1. there is at least one Hamiltonian walk in $(\omega,E)$,
  2. every Hamiltonian walk in $(\omega,E)$ visits every vertex infinitely-often?

Remarks.

  • A walk need not be injective, nor need it be surjective.

  • Condition 1. implies that $(\omega,E)$ is a connected graph.

  • In graph theory, an injective walk is called a path. (This is accidentally different from the usual convention in topology, where the term 'path' signals that self-intersections are permitted.)

  • In graph theory, a graph admitting an injective and surjective walk into it is called traceable. (For finite graphs, the term Hamiltonian most often means that there exists a Hamilton path whose end-vertices are adjacent, i.e., a Hamilton circuit. For infinite graphs, this does not make sense (simply because then a Hamilton path does not have two "end-vertices"), which necessitates either (0) keeping to the study of Hamilton-paths only, or (1) using definitions involving some kind of 'convergence'.) This explains the focus of this question on Hamilton-paths, and the title of the OP.

1This terminology harmonizes rather well with e.g. the book Futaba Fujie, Ping Zhang: Covering Walks in Graphs. SpringerBriefs in Mathematics, 2014.

$\endgroup$
  • $\begingroup$ Re " the proper term for a not necessarily injective "path" ": the usual convention is that this is just 'path'. For the record: 'path'='continuous map $[0,1]\to$(the space)', while 'arc'='map $[0,1]\to$(the space) which is a homeomorphism onto its image'. The latter condition is equivalent to 'injective' if (the space) is a Hausdorff space.) Note that this convention jarrs with the usual graph-theoretic convention which has 'path'='walk without any repetitions whatsoever'. This is just historical hazard. $\endgroup$ – Peter Heinig Sep 26 '17 at 12:46
  • 7
    $\begingroup$ Wouldn't a two-sided infinite path do? $\endgroup$ – Wojowu Sep 26 '17 at 12:56
  • $\begingroup$ @Dominic van der Zypen: extensive edits were made to your OP. I think that all these edits are right. In particular, the connectedness-condition was superfluous and misleading, unless I am missing something obvious. The term 'Hamiltonian walk' is an attested technical term. And Wojowu answered your question, and should perhaps make it an official answer. $\endgroup$ – Peter Heinig Sep 26 '17 at 14:01
  • 1
    $\begingroup$ What about an infinite tree with all vertex degrees equal to 3? This works even for a path infinite in both directions. $\endgroup$ – Ilya Bogdanov Sep 26 '17 at 15:38
  • 1
    $\begingroup$ What about $G=K_2$? $\endgroup$ – Jan Kyncl Sep 27 '17 at 0:04

Your Answer

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

Browse other questions tagged or ask your own question.