\((d, 1)\)-Total Labellings of Regular Nonbipartite Graphs and an Application to Flower Snarks

Abstract

A \((d,1)\)-totel labelling of a graph \(G\) is an assignment of integers to \(V(G) \cap 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 \(d\) in absolute value. The span of a \((d,1)\)-total labelling is the maximum difference between two labels. The minimum span of labels required for such a \((d, 1)\)-total labelling of \(G\) is called the \((d, 1)\)-total number and is denoted by \(\lambda_d^T(G)\). In this paper, we prove that \(\lambda_d^T(G)\geq d+r+1 \) for \(r\)-regular nonbipartite graphs with \(d \geq r \geq 3\) and determine the \((d, 1)\)-total numbers of flower snarks and of quasi flower snarks.