Edge colouring by total labellings

We introduce the concept of an edge-colouring total k-labelling. This is a labelling of the vertices and the edges of a graph G with labels 1, 2, . . . , k such that the weights of the edges define a proper edge colouring of G. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define X¬′t(G) to be the smallest integer k for which G has an edge-colouring total k-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree of G: ⌈( + 1)/2⌉ ≤ X¬′t(G) ≤ + 1. We improve the upper bound by 1 for every graph and prove a general upper bound of ¬X′t(G) ≤ /2 + O(√log). Moreover, we investigate some special classes of graphs