TY - JOUR
AU - Luiz, Atílio G.
AU - Campos, C. N.
PY - 2017
TI - The 1,2,3-Conjecture for powers of paths and powers of cycles
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da Computação
DO - 10.5753/etc.2017.3187
KW -
N2 - A labelling of a graph G is a mapping π : S → L, where L ⊂ R and S = E(G) or S = V (G) ∪ E(G). If S = E(G), π is an L-edge-labelling and, if S = V (G) ∪ E(G), π is an L-total-labelling. For each v ∈ V (G), the colour of v under π is defined as c π (v) = ∑ uv∈E(G) π(uv) if π is an L-edge-labelling; and c π (v) = π(v) + ∑ uv∈E(G) π(uv) if π is an L-total-labelling. The pair (π, c π ) is a neighbour-distinguishing-L-edge (total)-labelling if π : S → L is an edge (total)-labelling and c π (u) ≠ c π (v), for every edge uv ∈ E(G). The 1,2,3-Conjecture states that every simple graph with no isolated edge has a neighbour-distinguishing-L-edge-labelling with L = {1, 2, 3}. In this work, we verify the 1,2,3-Conjecture for powers of paths and powers of cycles and we also show that powers of cycles have a neighbour-distinguishing-{a, b}-total-labelling, a, b ∈ R, a ≠ b.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3187