×

On 3-step Hamiltonian trees. (English) Zbl 1334.05148

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.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite