Paper Info
Title
On Adjacent-vertex-distinguishing Total Colourings of Powers of Cycles, Hypercubes and Lattice Graphs.
Abstract
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.
Year
DOI
Venue
2019
10.1016/j.entcs.2019.08.005
Electronic Notes in Theoretical Computer Science
Keywords
Field
DocType
Adjacent-vertex-distinguishing total colouring,adjacent-vertex-distinguishing total chromatic number,lattice graphs,hypercubes,powers of cycles
Discrete mathematics,Graph,Lattice (order),Chromatic scale,Vertex (geometry),Computer science,Neighbourhood (graph theory),Conjecture,Hypercube,Bounded function
Journal
Volume
ISSN
Citations 
346
1571-0661
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
José D. Alvarado173.82
Simone Dantas211924.99
R. Marinho300.34