On Adjacent-vertex-distinguishing Total Colourings of Powers of Cycles, Hypercubes and Lattice Graphs

Given a graph G and a vertex v ∈ G, the chromatic neighbourhood of v is the set of colours of v and its incident edges. An adjacent-vertex-distinguishing total colouring (AVDTC) of a graph G is a proper total colouring of G which every two adjacent vertices on G have different chromatic neighbourhood. It was conjectured in 2005 that the minimum number of colours that guarantees the existence of an AVDTC of a graph G with these colours, χ a ″ ( G ) , is bounded from above by Δ(G) + 3 for any graph G. In this work we prove the validity of this conjecture for hypercubes, lattice graphs and powers of cycles Ckn when either (i) k = 2 and n ≥ 6, or (ii) n ≡ 0 (mod k + 1) through the construction of an explicit AVDTC which shows that χ a ″ ( G ) = Δ ( G ) + 2 for each of the preceding graph classes.