Some families of 0-rotatable graceful caterpillars - Luiz, Atílio G.; Campos, C. N.; Richter, R. Bruce (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
A graceful labelling of a tree T is an injective function f: V (T) → {0, 1, . . . , |E(T)|} such that {|f(u)−f(v)|: uv ∈ E(T)} = {1, 2, . . . , |E(T)|}. A tree T is said to be 0-rotatable if, for any v ∈ V (T), there exists a graceful labelling f of T such that f(v) = 0. In this work, it is proved that the follow- ing families of caterpillars are 0-rotatable: caterpillars with perfect matching; caterpillars obtained by identifying a central vertex of a path Pn with a vertex of K2; caterpillars obtained by identifying one leaf of the star K1,s−1 to a leaf of Pn, with n ≥ 4 and s ≥ ⌈n−1/2 ⌉; caterpillars with diameter five or six; and some families of caterpillars with diameter at least seven. This result reinforces the conjecture that all caterpillars with diameter at least five are 0-rotatable.