Lau, Gee-Choon; Ho, Yong-song; Lee, Sin-Min; Schaffer, Karl On 3-step Hamiltonian trees. (English) Zbl 1334.05148 J. Graph Label. 1, No. 1, 41-53 (2015). Summary: Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A \((p ,q)\)-graph \(G=(V,E)\) is said to have a \(k\)-step traversal if there exist a sequence of vertices \((v_1,v_2,\ldots,v_p)\) such for each \(i=1,2,\ldots,p-1\), the distance for \(v_i\) and \(v_{i+1}\) is equal to \(k\). A graph that admits a \(k\)-step traversal is called an \(\mathrm{AL}(k)\)-traversable graph. We call a graph \(G\) \(ak\)-step Hamiltonian graph if it is \(\mathrm{AL}(k)\)-traversal and \(d(v_p,v_1)=k\). In this paper, we present several constructions of 3-step Hamiltonian trees from smaller 3-step Hamiltonian trees. We show that every tree is an induced subtree of a 3-step Hamiltonian tree. This shows the impossibility to have a Kuratowski type characterization of 3-step Hamiltonian trees. Cited in 2 Documents MSC: 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) Keywords:\(k\)-step traversal; \(\mathrm{AL}(k)\)-traversable; \(k\)-step Hamiltonian trees PDFBibTeX XMLCite \textit{G.-C. Lau} et al., J. Graph Label. 1, No. 1, 41--53 (2015; Zbl 1334.05148)