Countable α-extendable graphs

Let us consider a countable graph G with vertex set V( G). Nash–Williams introduced the notion of an n-path, a 0- path is a finite path and for any n∈ N , an ( n+1)- path is a path P such that, for every finite subset F of V( G), P can be extended to an n-path containing F. This notion extends in a...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2001-08, Vol.239 (1), p.53-67
Main Authors: Rullière, Jean-Luc, Thomassé, Stéphan
Format: Article
Language:English
Subjects:
Extendable path
Hamiltonian path
Infinite graph
Locally finite path
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let us consider a countable graph G with vertex set V( G). Nash–Williams introduced the notion of an n-path, a 0- path is a finite path and for any n∈ N , an ( n+1)- path is a path P such that, for every finite subset F of V( G), P can be extended to an n-path containing F. This notion extends in a natural way to the concept of an α- path, where α is an ordinal. Polat proved that a countable graph which contains an ω 1-path has a hamiltonian path. The aim of this paper is to show that one cannot improve this theorem to an ordinal strictly less than ω 1: for any countable ordinal α, we exhibit a countable non-hamiltonian graph which contains an α-path. These graphs have maximal degree 4.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(00)00374-5