-Extendable paths in infinite graphs

Abstract: An -extendable path of a graph is defined inductively as follows: every path is 0-extendable; a path is ()-extendable if, for every finite , it has an -extendable extension which covers S; a path is -extendable for a limit ordinal if it is -extendable for every ordinal . Finally a path is -extendable if it is -extendable for every ordinal . If a graph has an -extendable path, then every countable set of its vertices is coverable by a (finite or infinite) path; in particular, if such a graph is countable then it has a Hamiltonian infinite path. We show that, for every graph G, there exists an ordinal such that every -extendable path of G is -extendable. The smallest of these ordinals is called the path-extendability rank of G. In this paper we study some properties of this ordinal. In particular we prove that the graphs for which almost all vertices have infinite degrees, and those whose thickness is finite and for which almost all vertices have finite degree, have a finite path-extendability rank. This gives partial answers to a problem of Nash-Williams (Proceedings of the Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1970, p. 547). [Copyright &y& Elsevier]