On 0-Rotatable Graceful Caterpillars
- PDF / 574,952 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 172 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
On 0-Rotatable Graceful Caterpillars Atı´lio G. Luiz1
•
C. N. Campos2 • R. Bruce Richter3
Received: 11 March 2019 / Revised: 14 August 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract An injection f : VðTÞ ! f0; . . .; jEðTÞjg of a tree T is a graceful labelling if fjf ðuÞ f ðvÞj : uv 2 EðTÞg ¼ f1; . . .; jEðTÞjg. Tree T is 0-rotatable if, for any v 2 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 K1;s1 to a leaf of a path Pn with n 3 and s dn2e; caterpillars with diameter five or six; and caterpillars T with diamðTÞ 7 such that, for every non-leaf vertex v 2 VðTÞ, the number of leaves adjacent to v is even and is at least 2 þ 2ððdiamðTÞ 1Þ mod 2Þ. These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable. Keywords Graceful labelling Graceful tree conjecture 0-rotatable
Mathematics Subject Classification MSC 05C78 MSC 05C05
& Atı´lio G. Luiz [email protected] C. N. Campos [email protected] R. Bruce Richter [email protected] 1
Campus Quixada´, Federal University of Ceara´, Ceara´, Brazil
2
Institute of Computing, University of Campinas, Sa˜o Paulo, Brazil
3
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
123
Graphs and Combinatorics
1 Introduction Let G ¼ ðVðGÞ; EðGÞÞ be a simple graph with vertex set V(G) and edge set E(G). A vertex labelling of G is an injective function f : VðGÞ ! Z 0 such that f(v) is the label of v 2 VðGÞ. Given a vertex labelling of G, define the (induced) label of uv 2 EðGÞ as the absolute difference of the labels of its ends, jf ðuÞ f ðvÞj. Denote LfV and LfE the sets of vertex and edge labels under f, respectively. Labelling f is a graceful labelling if LfV f0; . . .; jEðGÞjg and LfE ¼ f1; . . .; jEðGÞjg, in which case G is said to be graceful. A graceful labelling f of G is an a-labelling if, additionally, there exists an integer k 2 f0; . . .; jEðGÞjg such that, for each edge uv 2 EðGÞ, either f ðuÞ k\f ðvÞ or f ðvÞ k\f ðuÞ. Graceful labellings were introduced by Rosa [10], in 1966, who also posed the Graceful Tree Conjecture (GTC), which states that all trees are graceful. This conjecture was motivated and implies the Ringel-Kotzig Conjecture that, for any tree T with m edges, there is a cyclic decomposition of K2mþ1 into 2m þ 1 copies of T. The Graceful Tree Conjecture has turned out to be quite difficult. In his seminal paper, Rosa [10] proved that every caterpillar (that is, a tree in which all vertices are adjacent to vertices of a path in the tree) has a graceful labelling. Since then, much work has been done, which verified the conjecture for many subfamilies of trees. Nevertheless, in spite of ingenuity of the techniques employed, the Graceful Tree Conjecture remains open. Gallian
Data Loading...
