Article ID Journal Published Year Pages File Type
4650803 Discrete Mathematics 2008 18 Pages PDF
Abstract

A (p,1)(p,1)-total labelling of a graph G   is an assignment of integers to V(G)∪E(G)V(G)∪E(G) such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least p in absolute value. The span   of a (p,1)(p,1)-total labelling is the maximum difference between two labels. The minimum span of a (p,1)(p,1)-total labelling of G   is called the (p,1)(p,1)-total number   and denoted by λpT(G).We provide lower and upper bounds for the (p,1)(p,1)-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that λpT⩽Δ+2p-1 and give some evidences to support it. Finally, we determine the exact value of λpT(Kn), except for even n   in the interval [p+5,6p2-10p+4][p+5,6p2-10p+4] for which we show that λpT(Kn)∈{n+2p-3,n+2p-2}.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,