$(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)\ge d+r+1$ for $r$-regular nonbipartite graphs with $d\ge r\ge 3$ and determine the $(d,1)$-total numbers of flower snarks and of quasi flower snarks.