On 0-Rotatable Graceful Caterpillars

An injection \(f :V(T) \rightarrow \{0,\ldots ,|E(T)|\}\) of a tree T is a graceful labelling if \(\{|f(u)-f(v)| :uv \in E(T)\}=\{1,\ldots ,|E(T)|\}\). Tree T is 0-rotatable if, for any \(v \in V(T)\), there exists a graceful labelling f of T such that \(f(v)=0\). In this work, the following families of caterpillars are proved to be 0-rotatable: caterpillars with a perfect matching; caterpillars obtained by linking one leaf of the star \(K_{1,s-1}\) to a leaf of a path \(P_n\) with \(n \ge 3\) and \(s \ge \lceil \frac{n}{2} \rceil \); caterpillars with diameter five or six; and caterpillars T with \(\mathrm {diam}(T) \ge 7\) such that, for every non-leaf vertex \(v \in V(T)\), the number of leaves adjacent to v is even and is at least \(2+2((\mathrm {diam}(T)-1)\bmod {2})\). These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable.

This work was funded by São Paulo Research Foundation (FAPESP) grants 2014/16987-1, 2014/16861-8, 2015/03372-1; and NSERC grant 41705-2014 057082.

Authors and Affiliations

1. Campus Quixadá, Federal University of Ceará, Ceará, Brazil

   Atílio G. Luiz

2. Institute of Computing, University of Campinas, São Paulo, Brazil

   C. N. Campos

3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

   R. Bruce Richter

Corresponding author

Correspondence to Atílio G. Luiz.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Reprints and permissions