\((p,1)\)-total labelling of graphs (Q2467731)

Let \(V\) and \(E\) denote respectively the set of vertices and the set of edges of a graph \(G\). A \((p,1)\)-total labelling of \(G\) means assigning integers to \(V\cup E\) satisfying the following (i) and two adjacent vertices of \(G\) carry distinct integers, (ii) any two adjacent edges of \(G\) are assigned distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least \(|p|\) which is the absolute value of \(p\). The maximum difference between two labels is called the span of a \((p, 1)\)-total labelling. The \((p, 1)\)-total number denoted by \(\lambda^T_p(G)\), of \(G\) is the minimum span of a \((p,1)\)-total labelling of \(G\). In this paper, the authors provide lower and upper bounds for \(\lambda^T_p(G)\), and discuss bounds for the \((p,1)\)-total number \(\lambda^T_p(G)\) as a function of the maximum degree \(\Delta\) of \(G\). It is conjectured here that \(\lambda^T_p(G)\leq(\Delta+ 2p-1)\), and the exact value of \(\lambda^T_p(k_n)\) is obtained except when \(n\) is even and is in the interval \([p+5, 6p^2- 10p+ 4]\) for which it is shown that \(\lambda^T_p(k_n)\in [n+ 2p- 3, n+ 2p- 2]\).