The 1,2,3-Conjecture for powers of paths and powers of cycles

  • Atílio G. Luiz
  • C. N. Campos

Resumo


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 2 V (G), the colour of v under is defined as c (v) = Puv2E(G) (uv) if is an L-edgelabelling; and c (v) = (v) + Puv2E(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) 6= c (v), for every edge uv 2 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 = f1; 2; 3g. 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-fa; bg-totallabelling, a; b 2 R, a 6= b.

Publicado
06/07/2017
Como Citar

Selecione um Formato
LUIZ, Atílio G.; CAMPOS, C. N.. The 1,2,3-Conjecture for powers of paths and powers of cycles. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3187.