Countable -extendable graphs

DOI10.1016/S0012-365X(00)00374-5MaRDI QIDQ5946747zbMATH OpenOpenAlexFDO

Authors Jean-Luc Rullière, Stéphan Thomassé

Publication date 16 April 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00374-5

zbMATH Keywords

extendable pathHamiltonian infinite graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

For \(G\) a countable graph, Nash-Williams defined inductively an \(n\)-path in \(G\) as follows: A 0-path is a finite path in \(G\) and an \((n+1)\)-path is a finite path \(P\) such that, for every finite subset \(F\) of vertices of \(G\), \(P\) can be extended to an \(n\)-path containing \(F\). He showed that there is a countable non-Hamiltonian graph with vertices of infinite degree, which contains an \(n\)-path for every positive integer \(n\). In this paper, the authors extend the above definition to an \(\alpha\)-path, where \(\alpha\) is an ordinal. They construct, for any countable ordinal \(\alpha\), a non-Hamiltonian countable \(\alpha\)-extendable graph of vertex degree at most 4.

Recommendations

• \(\alpha\)-extendable paths in infinite graphs
• Countable connected-homogeneous graphs
• On the order of countable graphs
• The poset of morphism-extension classes of countable graphs
• A note onn-extendable graphs
• On almost 1-extendable graphs
• On the existence of countable universal graphs
• scientific article; zbMATH DE number 1263931
• scientific article; zbMATH DE number 734454
• The countable character of uncountable graphs

Cited in

(1)

• \(\alpha\)-extendable paths in infinite graphs

This page was built for publication: Countable \(\alpha\)-extendable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946747)