Some families of 0-rotatable graceful caterpillars

• Atílio G. Luiz UNICAMP
• C. N. Campos UNICAMP
• R. Bruce Richter University of Waterloo

DOI: https://doi.org/10.5753/etc.2016.9831

Resumo

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.

 

Referências

Broersma, A. J. and Hoede, C. (1999). Another equivalent of the graceful tree conjecture. Ars Combinatoria, 51:183–192.

Bussel, F. V. (2004). 0-Centred and 0-ubiquitously graceful trees. Discrete Mathematics, 277:193–218.

Chung, F. R. K. and Hwang, F. K. (1981). Rotatable graceful graphs. Ars Combinatoria, 11:239–250.

Gallian, J. A. (2015). A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, DS6, 1–389.

Hrnciar, P. and Haviar, A. (2001). All trees of diameter five are graceful. Discrete Mathematics, 233:133–150.

Rosa, A. (1967). On certain valuations of the vertices of a graph. Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 349–355.

Rosa, A. (1977). Labeling snakes. Ars Combinatoria, 3:67–73.