Neighbour-distinguishing labellings of powers of paths and powers of cycles

Author(s)

Luiz, Atilio G. ^[1] ; Campos, C. N. ^[2] ; Dantas, Simone ^[3] ; Sasaki, Diana ^[4]

Affiliation

^[1] Univ Fed Ceara, Campus Quixada, BR-63902580 Quixada, Ceara - Brazil

^[2] Univ Estadual Campinas, Inst Comp, Sao Paulo - Brazil

^[3] Fluminense Fed Univ, Inst Math & Stat, Niteroi, RJ - Brazil

^[4] Univ Estado Rio De Janeiro, Inst Math & Stat, Rio De Janeiro - Brazil

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 39, n. 4 FEB 2020.
• Web of Science Citations: 0

Abstract

Alabelling of a graph G is a mapping pi : S. L, where L. Rand S. V(G). E(G). If S subset of E(G), p is an L-edge-labelling and, if S = V(G). E(G), p is an Ltotal-labelling. For each v. V(G), the colour of v under p is defined as Cp (v) = Sigma uv. E(G) p(uv) if p is an L-edge-labelling; and Cp (v) = p(v)+ Sigma uv.E(G) p(uv) if p is an L-total-labelling. Labelling p is a neighbour-distinguishing L-edge-labelling (neighbour-distinguishing L-total-labelling) if p is an L-edge-labelling (L-totallabelling) and Cp (u) = Cp (v), for every edge uv. E(G). In 2004, Karonski, Luczac and Thomasson posed the 1,2,3-Conjecture, which states that every simple graph with no isolated edge has a neighbour-distinguishing [1, 2, 3]-edge-labelling. In 2010, Przybylo and Wozniak posed the 1,2-Conjecture, which states that every simple graph has a neighbour- distinguishing [1, 2]-total-labelling. In this work, we contribute to the study of these conjectures by verifying the 1,2,3-Conjecture and 1,2-Conjecture for powers of paths and powers of cycles. We also obtain generalizations of these results: we prove that all powers of paths have neighbour-distinguishing [t, 2t]-totallabellings and neighbour-distinguishing [t, 2t, 3t]-edge-labellings, for t. R\textbackslash{}[0]; and we prove that all powers of cycles have neighbour-distinguishing [a, b]-totallabellings, and neighbour-distinguishing [t, 2t, 3t]-edge-labellings, for a, b, t. R, a not equal b and t not equal 0 (AU)

• FAPESP's process: 14/16987-1 - Selected structural problems in graph theory
• Grantee: Christiane Neme Campos
• Support Opportunities: Scholarships abroad - Research