A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES
Koich Yamazaki, Seiichi Tani, Tetsuro Nishino · International Journal of Foundations of Computer Science · 2001
Let G be a k-tree such that |{v ∈ V(G): degG(v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to Pn,k. In this way, we give a new characterization of k-th power (i.e. Pn,k) of paths with n vertices in terms of k-trees.