On 0-Rotatable Graceful Caterpillars

Autor(es)

Luiz, Atilio G. ; Campos, C. N. ; Richter, R. Bruce

• Tipo de documento: Artigo Científico
• Fonte: GRAPHS AND COMBINATORICS; v. 36, n. 6, p. 19-pg., 2020-09-03.

Resumo

An injection f:V(T)->{0,...,vertical bar E(T)vertical bar} of a tree T is a graceful labelling if {vertical bar f(u)-f(v)vertical bar:uv is an element of E(T)}={1,..., vertical bar E(T)vertical bar}. Tree T is 0-rotatable if, for any v is an element of 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,K-s-1 to a leaf of a path P-n with n >= 3 and s >= left [n/2]; caterpillars with diameter five or six; and caterpillars T with diam (T)>= 7 such that, for every non-leaf vertex v is an element of V(T), the number of leaves adjacent tovis even and is at least 2+2((diam(T)-1)mod2). These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable. (AU)

• Processo FAPESP: 14/16861-8 - Problemas de rotulação em grafos
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/16987-1 - Problemas estruturais em teoria de grafos
• Beneficiário: Christiane Neme Campos
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Processo FAPESP: 15/03372-1 - Problemas de rotulação em grafos
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado