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

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

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 ∈ 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.

Referências

Dudek, A. and Wajc, D. (2011). On the complexity of vertex-coloring edge-weightings. Discrete Mathematics and Theoretical Computer Science, 13(3):45–50.

Hulgan, J., Lehel, J., Ozeki, K., and Yoshimoto, K. (2016). Vertex Coloring of Graphs by Total 2-Weightings. Graphs and Combinatorics, 32(6):2461–2471.

Kalkowski, M., Karónski, M., and Pfender, F. (2010). Vertex-coloring edge-weightings: Toward the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B, 100(3):347–349.

Karónski, M., Łuczak, T., and Thomason, A. (2004). Edge weights and vertex colours. Journal of Combinatorial Theory, Series B, 91(1):151–157.

Luiz, A. G., Campos, C. N., Dantas, S., and Sasaki, D. (2015). The 1,2-Conjecture for powers of cycles. Electronic Notes in Discrete Mathematics, 50:83–88.

Luiz, A. G., Campos, C. N., Dantas, S., and Sasaki, D. (2017). The 1,2-conjecture for powers of paths and powers of cycles. (submmited).

Przybyło, J. and Woźniak, M. (2010). On a 1,2 Conjecture. Discrete Mathematics and Theoretical Computer Science, 12(1):101–108.

Seymour, P. D. (1995). Nowhere-zero flows. In Handbook of combinatorics (eds. Graham, R. L., Grotschel, M., and Lovasz, L.), North-Holand, Amsterdam, pages 289–299.

Thomassen, C., Wu, Y., and Zhang, C.-Q. (2016). The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B, 121:308–325.
Publicado
02/07/2017
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 . p. 41-44. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3187.