Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

\((d,1)\)-Total labellings of two infinite families of snarks

Zhiqiang Gao1, Chunling Tong1, XingKuan Bai1, Wenzheng An1
1School of Information Science and Electricity Engineering, Shandong Jiaotong University, Jinan 250357, China
  • Received: 26/03/2024
  • Accepted: 16/09/2024
  • Published Online: 17/03/2025

Abstract

A \((d, 1)\)-total labelling of a graph \(G\) is an assignment of integers \(\{0,1,\cdots,l\}\) to the vertices and edges of the graph such that adjacent vertices receive distinct integers, adjacent edges receive distinct integers, and the integer received by a vertex differs at least \(d\) from those received by its incident edges. The minimum number \(l\) required for such an assignment is called the \((d, 1)\)-total number of the graph \(G\). This paper contributes to \((d,1)\)-total labelling of two infinite families of snarks, the Goldberg family and the Loupekhine family. We completely determine the \((d,1)\)-total numbers of these two families of snarks for all \(d\geq2\).

Keywords: graph labelling, (d,1)-total labelling, (d,1)-total number, Goldberg snark, Loupekhine snark

1. Introduction

Graph labelling is an assignment of integers to elements of a graph, i.e. vertices and/or edges, such that the integers assigned to adjacent elements fulfill certain requirements. Various labellings have been put forward based on different requirements [8]. Among them, an intensively studied one is known as \(L(2,1)\)-labelling. It is an assignment of integers to the vertices such that adjacent vertices receive integers with difference at least \(2\), and vertices of distance two receive distinct integers [12]. A natural generalization of \(L(2,1)\)-labelling is \(L(d,1)\)-labelling. Further, \(L(d,1)\)-labelling is applied to the incidence graph \(s(G)\), a graph obtained from \(G\) by inserting one vertex along each edge of \(G\) [30].

The \(L(d,1)\)-labelling of \(s(G)\) is equivalent to an assignment of integers to both the vertices and edges of \(G\), which then leads to the notion of \((d, 1)\)-total labelling of \(G\) [15,13].

\((d, 1)\)-Total labelling of a graph \(G\) is an assignment of integers \(\{0,1,2,\cdots,l\}\) to the vertices \(V(G)\) and edges \(E(G)\) such that adjacent vertices receive distinct integers, adjacent edges receive distinct integers, and the integer received by a vertex differs at least \(d\) from those received by its incident edges. It can be also regarded as a generalization of total colouring. The main issue in the study of \((d, 1)\)-total labelling is to find the minimum number \(l\) required for such an assignment, which is particularly called as the \((d, 1)\)-total number of the graph \(G\), denoted as \(\lambda^{\small{\mbox{T}}}_{d}(G)\). However, it is a difficult problem to determine the exact value of \((d, 1)\)-total number for a graph in general, and it is also nontrivial even to find its tight bound.

This issue has received increasing attention. So far, great efforts have been directed towards studying \((d, 1)\)-total labellings of graphs, and some progress has been made. Havet and Yu conjectured that \(\lambda^{\small{\mbox{T}}}_{d}(G)\leq \Delta(G)+2d – 1\), where \(\Delta(G)\) is the maximum degree of \(G\) [16]. The validity of conjecture has been verified for complete graphs [4,16], bipartite graphs [18,14], planar graphs [1,3,31,25,26,22,21] and graphs with a given maximum average degree [20]. The exact values of \((d,1)\)-total numbers have been determined for some graphs such as flower snarks [28], generalized Petersen graphs [27], Sierpiński-like graphs [5], and joins of paths and cycles [29].

Snarks are the cubic bridgeless graphs that are not 3-edge colorable. The interest in snarks partly arises from the fact that several well-known conjectures have snarks as counterexamples. Two important families of snarks are Goldberg snarks and Loupekhine snarks. A number of articles have been devoted to studying the labelling and colouring of them, such as their \(L(2,1)\)-labelling[19], edge colourings [7,6,9] and total colouring [2,24,11,23].

However, the \((d, 1)\)-total numbers of them still remain open. To fill the gap, in this paper, we study the \((d,1)\)-total labelling of the two infinite families of snarks. We aim to determine the \((d,1)\)-total numbers of them for all \(d\geq 2\).

This paper is organized as follows. In Section 2, we determine the \((d,1)\)-total numbers of Goldberg snarks. In Section 3, we determine the \((d,1)\)-total numbers of Loupekhine snarks. Section 4 is our conclusion.

2. (d,1)-Total labelling of Goldberg snarks

2.1. The definitions of Goldberg snarks and their related graphs

A Goldberg snark \(G_{k}\) for odd \(k\geq 3\) is defined by \(V (G_{k}) = \{v^{i} _{j}|0 \leq i \leq k-1, 1\leq j \leq 8\}\) and \(E (G_{k})\) ={\(v^{i}_{1}v^{i}_{2},v^{i}_{2}v^{i}_{3}, v^{i}_{3}v^{i}_{4}, v^{i}_{4}v^{i}_{5},v^{i}_{5}v^{i}_{1}, v^{i}_{1}v^{i}_{7},v^{i}_{4}v^{i}_{8},v^{i}_{7}v^{i}_{8},v^{i}_{5}v^{i}_{6},\) \(v^{i}_{6}v^{i+1}_{6},v^{i}_{2}v^{i+1}_{3},v^{i}_{8}v^{i+1}_{7}: 0 \leq i \leq k-1\) }, where the superscripts are considered modulo \(k\) [10].

The graph gained from \(G_{k}\) by replacing the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) with the new edges \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) is called a twisted Goldberg snark, denoted as \(TG_{k}\) for odd \(k\geq3\).

Without ambiguity, both the graphs \(G_{k}\) and \(TG_{k}\) for odd \(k\geq 3\) are refereed to as Goldberg family of snarks, while \(G_k\) and \(TG_k\) for even \(k\geq 4\) are refereed to as the related graphs of Goldberg snarks. Figure 1 shows Goldberg snark \(G_{3}\), twisted Goldberg snark \(TG_{3}\), and the related graphs \(G_{4}\) and \(TG_{4}\). Note that we have drawn \(G_{k}\) and \(TG_{k}\) in one figure, where the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(G_{k}\) are with full lines while \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(TG_{k}\) are with dashed lines.

Figure 1 \(G_{3}(TG_{3})\) and \(G_{4}(TG_{4})\)

2.2. (2,1)-Total labelling of Goldberg snarks and their related graphs

We prove that the \((2,1)\)-total number of \(G_k\) and \(TG_k\) is 5 in this section. To this end, we first demonstrate Lemma 2.1, which provides an upper bound of \(\lambda^{T}_{2}(G_k(TG_k))\).

Lemma 2.1. \(\lambda^{T}_{2}(G_{k}(TG_{k}))\leq5\) for \(k\geq3\).

Proof. We use \(f\) to represent an assignment of integers to vertices and edges of \(G_k\). It is defined as Table 1 for odd \(k\), and Table 2 for even \(k\).

Table 1 \(f(G_{k})\) for odd \(k\)
\(i\) \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\) \(f(v^i_5v^i_6)\) \(f(v^i_6v^i+1_6)\)
even(\(\leq\)k-3) 4 5 3 0 5 3 1 2 4 2
odd 5 0 1 0 2 4 3 5 1 3
k-1 0 5 2 3 2 3 0 5 4 5
Table 2 \(f(G_{k})\) for even \(k\)
   \(i\)   \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\) \(f(v^i_5v^i_6)\) \(f(v^i_6v^i+1_6)\)
even 3 2 5 4 5 4 0 2 3 0
odd 0 1 5 4 5 4 0 2 2 1

Here, \(f\) defined by Table 1 and Table 2 is also applicable to \(TG_{k}\). The only difference is that the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(G_{k}\) are replaced with \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(TG_{k}\), and there are \(f(v^{k-1}_{2}v^{0}_{7}) =f(v^{k-1}_{2}v^{0} _{3})\) and \(f(v^{k-1}_{8}v^{0}_{3})=f(v^{k-1}_{8}v^{0}_{7})\). Figure 2 shows the labellings of \(G_3(TG_3)\) and \(G_4(TG_4)\) based on the above assignment \(f\).

Figure 2 \(f(G_3(TG_3))\) and \(f(G_4(TG_4))\) defined by Table 1 and Table 2

To show that the assignment \(f\), defined by Table 1 and Table 2, is a \((2,1)\)-total labelling of \(G_k(TG_k)\), we examine the labelling of each vertex and edge. For example, we consider the vertex \(v^{0}_{1}\) of \(G_k(TG_k)\) for odd \(k\), to which three vertices \(v^{0}_{2}\), \(v^{0}_{5}\) and \(v^{0}_{7}\) are adjacent. According to Table 1, there are \(f(v^{0}_{1}) = 1, f(v^{0}_{2}) = 0, f(v^{0}_{5}) = 2, f(v^{0}_{7}) = 0, f(v^{0}_{1}v^{0}_{2}) = 4, f(v^{0}_{5}v^{0}_{1}) = 5, f(v^{0}_{1}v^{0}_{7}) = 3\). It follows \(f(v^{0}_{1})\neq f(v^{0}_{2}),f(v^{0}_{1})\neq f(v^{0}_{5}),f(v^{0}_{1})\neq f(v^{0}_{7})\), \(f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{5}v^{0}_{1}), f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{1}v^{0}_{7}), f(v^{0}_{5}v^{0}_{1}) \neq f(v^{0}_{1}v^{0}_{7})\) and \(|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{2})|,|f(v^{0}_{1})- f(v^{0}_{5}v^{0}_{1})|,|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{7})| \geq 2\). Similarly, we can examine the labellings of \(v^{0}_{1}\) for even \(k\) and all the other vertices and edges, and verify that they also fulfill the requirements of a \((2,1)\)-total labelling. That is, the assignment fulfills the three requirements: adjacent vertices receive distinct integers, adjacent edges receive distinct integers, and the integer received by a vertex differs at least 2 from those received by its incident edges. Therefore, the assignment \(f\), defined by Table 1 and Table 2, gives a \((2,1)\)-total labelling of \(G_k(TG_k)\).

Noting that the integers used in the assignment are \(\{0,1,\cdots,5\}\), we obtain that the \((2,1)\)-total number of \(G_{k}(TG_{k})\) for \(k\geq3\) must be less than or equal to \(5\). This completes the proof of Lemma 2.1. ◻

On the other hand, for a \(\Delta\)-regular graph \(G\), there is always \(\lambda^{T}_{d}(G)\geq d+\Delta\) [16]. Since \(\Delta(G_k(TG_k))=3\), we have Lemma 2.2.

Lemma 2.2. \(\lambda^{\mbox{T}}_{2}(G_k(TG_k))\geq 5\) for \(k\geq 3\).

Lemma 2.1 and Lemma 2.2 give the upper bound and lower bound of \(\lambda^{T}_{2}(G_k(TG_k))\) respectively, both of which are \(5\). Hence, we have Theorem 2.3.

Theorem 2.3. \(\lambda^{\mbox{T}}_{2}(G_k(TG_k))= 5\) for \(k\geq 3\).

2.3. (d,1)-Total labelling of Goldberg snarks and their related graphs

We prove that the (\(d\),1)-total number of \(G_k(TG_k)\) is \(d+4\) in this section. To this end, we demonstrate Lemma 2.4.

Lemma 2.4. \(\lambda^{\mbox{T}}_{d}(G_k(TG_k))\leq d+4\) for \(k\geq 3\).

Proof. Let \(f\) be an assignment of integers to vertices and edges of \(G_k\). It is defined as Table 3 for odd \(k\), and Table 4 for even \(k\).

Table 3 \(f(G_{k})\) for odd \(k\)
\(i\) \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\) \(f(v^i_5v^i_6)\) \(f(v^i_6v^i+1_6)\)
even(\(\leq\)k-3) d+4 d+1 d+4 d+1 d+2 d+3 d+3 d+1 d+4 d+2
odd d+4 d+1 d+4 d+1 d+2 d+3 d+3 d+1 d+4 d+3
k-1 d+4 d+3 d+1 d+3 d+2 d+1 d+4 d+3 d+4 d+1
Table 4 \(f(G_{k})\) for even \(k\)
\(i\) \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\) \(f(v^i_5v^i_6)\) \(f(v^i_6v^i+1_6)\)
even d+4 d+1 d+4 d+1 d+2 d+3 d+3 d+1 d+3 d+2
odd d+4 d+3 d+1 d+3 d+2 d+1 d+4 d+3 d+4 d+1

Here, \(f\) defined by Table 3 and Table 4 is also applicable to \(TG_{k}\), if we replace the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(G_{k}\) with \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(TG_{k}\), and let \(f(v^{k-1}_{2}v^{0}_{7}) =f(v^{k-1}_{2}v^{0} _{3})\) and \(f(v^{k-1}_{8}v^{0}_{3})=f(v^{k-1}_{8}v^{0}_{7})\). Figure 3 shows the labellings of \(G_3(TG_3)\) and \(G_4(TG_4)\) based on the above assignment \(f\).

Figure 3 \(f(G_3(TG_3))\) and \(f(G_4(TG_4))\) defined by Table 3 and Table 4

By examining the labellings of vertices and edges, we can find that the assignment \(f\), defined by Table 3 and Table 4, gives a \((d,1)\)-total labelling of \(G_k(TG_k)\). That is, the assignment fulfills the three requirements: adjacent vertices receive distinct integers, adjacent edges receive distinct integers, and the integer received by a vertex differs at least \(d\) from those received by its incident edges. For example, we consider the vertex \(v^{0}_{1}\) of \(G_k(TG_k)\) for odd \(k\). According to Table 3, there are \(f(v^{0}_{1}) = 2, f(v^{0}_{2}) = 0, f(v^{0}_{5}) = 1, f(v^{0}_{7}) = 0, f(v^{0}_{1}v^{0}_{2}) = d+4, f(v^{0}_{5}v^{0}_{1}) =d+2, f(v^{0}_{1}v^{0}_{7}) = d+3\). It follows \(f(v^{0}_{1})\neq f(v^{0}_{2}),f(v^{0}_{1})\neq f(v^{0}_{5}),f(v^{0}_{1})\neq f(v^{0}_{7})\), \(f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{5}v^{0}_{1}), f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{1}v^{0}_{7}), f(v^{0}_{5}v^{0}_{1}) \neq f(v^{0}_{1}v^{0}_{7})\) and \(|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{2})|,|f(v^{0}_{1})- f(v^{0}_{5}v^{0}_{1})|,|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{7})| \geq d\). Similarly, we can examine the labellings of \(v^{0}_{1}\) for even \(k\) and all the other vertices and edges, and verify that they fulfill the requirements of a \((d,1)\)-total labelling of \(G_k(TG_k)\).

Since the integers used in the assignment are \(\{0,1,\cdots,d+4\}\), we obtain that the \((d, 1)\)-total number of \(G_k(TG_k)\) for \(k\geq3\) must be less than or equal to \(d+4\). This completes the proof of Lemma 2.4. ◻

On the other hand, \(G_k(TG_k)\) is a \(3\)-regular nonbipartite graph. By borrowing the result obtained in Ref. [28], which indicates \(\lambda^{T}_{d}(G) \geq d + \Delta +1\) if \(G\) is an \(\Delta\)-regular nonbipartite graph and \(d\geq \Delta\geq 3\), we have Lemma 2.5.

Lemma 2.5. \(\lambda^{\mbox{T}}_{d}(G_k(TG_k))\geq d+4\) for \(k,d\geq 3\).

By combining Lemmas 2.4 and 2.5, we have Theorem 2.6.

Theorem 2.6. \(\lambda^{\mbox{T}}_{d}(G_k(TG_k))= d+4\) for \(k,d\geq 3\).

3. (d,1)-Total labelling of Loupekhine snarks

3.1. The definition of Loupekhine snarks

The first kind of Loupekhine snark \(LO_{k}\)–\(I\) for odd \(k\geq 3\) is similar to Goldberg snark \(G_{k}\). Specially, \(LO_{3}\)–\(I\) is the graph gained from \(G_{3}\) when central triangle of \(G_{3}\) is contracted to a vertex, as shown in Figure 4(a), and \(LO_{k}\)–\(I\) for odd \(k \geq 5\) is recursively constructed by adding the link graph to \(LO_{k-2}\)–\(I\) [17], as shown in Figure 4(b). \(LO_{k}\)–\(I\) is shown as Figure 4(c), where \(t\) denotes \(\frac{k-1}{2}\) for simplicity.

The second kind of Loupekhine snark \(LO_{k}\)–\(II\) for odd \(k\geq3\) is defined from \(LO_{k}\)–\(I\) by replacing the edges \(v^{k-1}_{2}v^{0}_{3}\) and \(v^{k-1} _{8}v^{0}_{7}\) with the new edges \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\). Both the first and second kinds of Loupekhine snarks, \(LO_{k}\)–\(I\) and \(LO_{k}\)–\(II\), are refereed to as Loupekhine family of snarks.

Figure 4 The Loupekine snark \(LO_{3}\)-I, the link graph and \(LO_{k}\)-I

3.2. (2,1)-Total labelling of Loupekhine snarks

We prove that the \((2,1)\)-total number of \(LO_k\)–\(I\) and \(LO_k\)–\(II\) is 5 in this section. To this end, we first demonstrate Lemma 3.1.

Lemma 3.1. \(\lambda^{T}_{2}(LO_{k}\)–\(I\)(\(LO_{k}\)–\(II))\leq5\) for odd \(k\geq3\).

Proof. We use \(f\) to represent an assignment of integers to vertices and edges of \(LO_{k}\)–\(I\) for odd \(k \geq 3\). The assignment for most of vertices and edges of \(LO_{k}\)–\(I\) is defined as Table 5, and for the others are defined as follows: \(f(v_{6})=0\), \(f(v^{0}_{5}v_{6})=3\), \(f(v^{\frac{k-1}{2}}_{5}v_{6})=5\), \(f(v^{k-1}_{5}v_{6})=2\) and \(f(v^{i}_{5}v^{k-1-i}_{5})=2\) (\(1\leq i\leq k-2\)  and  \(i\neq\frac{k-1}{2})\).

Table 5 \(f(LO_{k}\)-\(I\)) for odd \(k \geq 3\)
\(i\) \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\)
\(<\tfrac{k-1}{2}\) 5 4 2 1 0 4 0 2
\(=\tfrac{k-1}{2}\) 5 4 2 1 0 4 0 2
\(>\tfrac{k-1}{2}\) 5 4 5 1 0 4 0 2

Here, \(f\) defined by Table 5 with the formulas above it is also applicable to \(LO_k\)–\(II\) if we replace the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(LO_k\)–\(I\) with \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(LO_k\)–\(II\), and let \(f(v^{k-1}_{2}v^{0}_{7}) =f(v^{k-1}_{2}v^{0} _{3})\) and \(f(v^{k-1}_{8}v^{0}_{3})=f(v^{k-1}_{8}v^{0}_{7})\). Figure 5 shows the labellings of \(LO_3\)–\(I\)(\(LO_3\)–\(II\)) and \(LO_5\)–\(I\)(\(LO_5\)–\(II\)) based on the above assignment \(f\). Note that \(LO_k\)–\(I\) and \(LO_k\)–\(II\) are drawn in one figure, where the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(LO_k\)–\(I\) are with full lines while \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(LO_k\)–\(II\) are with dashed lines.

Figure 5 \(f(LO_3\)-\(I(LO_3\)-\(II))\) and \(f(LO_5\)-\(I\)(\(LO_5\)-\(II\))) defined by Table 5 with the formulas above it

By examining the labellings of vertices and edges, we can find that the assignment \(f\), defined by Table 5 with the formulas above it, is a \((2,1)\)-total labelling of \(LO_k\)–\(I(LO_k\)–\(II)\). Again, we take the vertex \(v^{0}_{1}\) as an example to illustrate this. According to Table 5, there are \(f(v^{0}_{1}) = 2, f(v^{0}_{2}) = 1, f(v^{0}_{5}) = 5, f(v^{0}_{7}) = 0, f(v^{0}_{1}v^{0}_{2}) = 5, f(v^{0}_{5}v^{0}_{1}) =0, f(v^{0}_{1}v^{0}_{7}) =4\). It follows \(f(v^{0}_{1})\neq f(v^{0}_{2}),f(v^{0}_{1})\neq f(v^{0}_{5}),f(v^{0}_{1})\neq f(v^{0}_{7})\), \(f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{5}v^{0}_{1}), f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{1}v^{0}_{7}), f(v^{0}_{5}v^{0}_{1}) \neq f(v^{0}_{1}v^{0}_{7})\) and \(|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{2})|,|f(v^{0}_{1})- f(v^{0}_{5}v^{0}_{1})|,|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{7})| \geq 2\). Similarly, we can examine the labellings of all the other vertices and edges and verify that they fulfill the requirements of a \((2,1)\)-total labelling.

Since the integers used in the assignment are \(\{0,1,\cdots,5\}\), we obtain that the \((2,1)\)-total number of \(LO_k\)–\(I\)(\(LO_k\)–\(II\)) for \(k\geq3\) must be less than or equal to \(5\). This completes the proof of Lemma 3.1. ◻

On the other hand, according to Ref. [16], we have Lemma 3.2.

Lemma 3.2. \(\lambda^{\mbox{T}}_{2}\)(\(LO_{k}\)–\(I\)(\(LO_{k}\)–\(II\)))\(\geq\) 5 for odd \(k\geq 3\).

By combining Lemmas 3.1 and 3.2, we have Theorem 3.3.

Theorem 3.3. \(\lambda^{\mbox{T}}_{2}\)(\(LO_{k}\)–\(I\)(\(LO_{k}\)–\(II)\))= 5 for odd \(k\geq 3\).

3.3. \((d,1)\)-Total labelling of Loupekhine snarks

We prove that the (\(d\),1)-total number of \(LO_{k}\)–\(I\)(\(LO_{k}\)–\(II)\) is \(d+4\) in this section. To this end, we demonstrate Lemma 3.4.

Lemma 3.4. \(\lambda^{T}_{d}(LO_{k}\)–\(I\)(\(LO_{k}\)–\(II))\leq d+4\) for \(d\geq 3\) and odd \(k\geq3\) .

Proof. We use \(f\) to represent an assignment of integers to vertices and edges of \(LO_{k}\)–\(I\) for \(d\geq 3\) and odd \(k\geq3\). The assignment for most of vertices and edges of \(LO_{k}\)–\(I\) is defined as Table 6, and for the others are defined as follows: \(f(v_{6})=0\), \(f(v^{0}_{5}v_{6})=d+3, f(v^{\frac{k-1}{2}}_{5}v_{6})=d+1, f(v^{k-1}_{5}v_{6})=d+4\) and \(f(v^{i}_{5}v^{k-1-i}_{5})=d+4~(1\leq i\leq k-2\)  and  \(i\neq\frac{k-1}{2})\).

Table 6 \(f(LO_{k}\)-\(I\)) for \(d\geq 3\) and odd \(k\geq3\)
\(i\) \(f(v^i_1v^i_2)\) \(f(v^i_2v^i_3)\) \(f(v^i_3v^i_4)\) \(f(v^i_4v^i_5)\) \(f(v^i_5v^i_1)\) \(f(v^i_1v^i_7)\) \(f(v^i_4v^i_8)\) \(f(v^i_7v^i_8)\)
\(<\tfrac{k-1}{2}\) d+4 d+1 d+4 d+1 d+2 d+3 d+3 d+1
\(=\tfrac{k-1}{2}\) d+2 d+1 d+4 d+2 d+4 d+3 d+3 d+1
\(>\tfrac{k-1}{2}\) d+3 d+4 d+1 d+3 d+2 d+1 d+4 d+3

Here, \(f\) defined by Table 6 and the formulas above it is also applicable to \(LO_k\)–\(II\), if we replace the edges \(v^{k-1}_{2}v^{0} _{3}\) and \(v^{k-1}_{8}v^{0}_{7}\) of \(LO_k\)–\(I\) with \(v^{k-1}_{2}v^{0}_{7}\) and \(v^{k-1}_{8}v^{0}_{3}\) of \(LO_k\)–\(II\), and let \(f(v^{k-1}_{2}v^{0}_{7}) =f(v^{k-1}_{2}v^{0} _{3})\) and \(f(v^{k-1}_{8}v^{0}_{3})=f(v^{k-1}_{8}v^{0}_{7})\). Figure 6 shows the labellings of \(LO_3\)–\(I\)(\(LO_3\)–\(II\)) and \(LO_5\)–\(I\)(\(LO_5\)–\(II\)) based on the above assignment \(f\).

Figure 6 \(f(LO_3\)-\(I\)(\(LO_3\)-\(II\))) and \(f(LO_5\)-\(I\)(\(LO_5\)-\(II))\) defined by Table 6 with the formulas above it

By examining the labellings of vertices and edges of \(LO_k\)–\(I(LO_k\)–\(II)\), we can find that the assignment \(f\), defined by Table 6 with the formulas above it, is a \((d,1)\)-total labelling of \(LO_k\)–\(I(LO_k\)–\(II)\). We take the vertex \(v^{0}_{1}\) as an example again. According to Table 6, there are \(f(v^{0}_{1}) = 2, f(v^{0}_{2}) = 0, f(v^{0}_{5}) = 1, f(v^{0}_{7}) = 0, f(v^{0}_{1}v^{0}_{2}) =d + 4, f(v^{0}_{5}v^{0}_{1}) = d + 2, f(v^{0}_{1}v^{0}_{7}) = d + 3\). It follows \(f(v^{0}_{1})\neq f(v^{0}_{2}),f(v^{0}_{1})\neq f(v^{0}_{5}),f(v^{0}_{1})\neq f(v^{0}_{7})\), \(f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{5}v^{0}_{1}), f(v^{0}_{1}v^{0}_{2}) \neq f(v^{0}_{1}v^{0}_{7}), f(v^{0}_{5}v^{0}_{1}) \neq f(v^{0}_{1}v^{0}_{7})\) and \(|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{2})|,|f(v^{0}_{1})- f(v^{0}_{5}v^{0}_{1})|,|f(v^{0}_{1})- f(v^{0}_{1}v^{0}_{7})| \geq d\).

Since the integers used in the assignment are \(\{0,1,\cdots,d+4\}\), we obtain that the \((d, 1)\)-total number of \(LO_k\)–\(I\)(\(LO_k\)–\(II\)) for \(d\geq 3\) and odd \(k\geq3\) must be less than or equal to \(d+4\). This completes the proof of Lemma 3.4. ◻

On the other hand, \(LO_k\)–\(I\)(\(LO_k\)–\(II\)) is a \(3\)-regular nonbipartite graph. By borrowing the result obtained in Ref. [28], we have Lemma 3.5.

Lemma 3.5. \(\lambda^{\mbox{T}}_{d}\)(\(LO_k\)–\(I\)(\(LO_k\)–\(II\)))\(\geq d+4\) for \(d\geq 3\) and odd \(k\geq3\).

By combining Lemmas 3.4 and 3.5, we have Theorem 3.6.

Theorem 3.6. \(\lambda^{\mbox{T}}_{d}\)(\(LO_k\)–\(I\)(\(LO_k\)–\(II\)))\(= d+4\) for \(d\geq 3\) and odd \(k\geq3\).

4. Conclusion

In conclusion, we have presented \((d,1)\)-total labellings of Goldberg family and Loupekhine family, and obtained the exact values of \((d,1)\)-total numbers of the two infinite families of snarks for all \(d\geq 2\). Besides, we have also given the exact values of \((d,1)\)-total labellings of the related graphs of Goldberg snarks. The \((2,1)\)-total number and \((d,1)\)-total number for \(d\geq 3\) are 5 and \(d+4\), respectively, for all of them.

Conflict of Interest

The authors declares no conflict of interests.

Acknowledgment

We are grateful to the anonymous referee whose helpful suggestions have led to an improvement of this paper.

References:

  1. F. Bazzaro, M. Montassier, and A. Raspaud. (d, 1)-total labelling of planar graphs with large girth and high maximum degree. Discrete Mathematics, 307(16):2141–2151, 2007. https://doi.org/10.1016/j.disc.2005.12.059.
  2. C. Campos, S. Dantas, and C. P. de Mello. The total-chromatic number of some families of snarks. Discrete Mathematics, 311(12):984–988, 2011. https://doi.org/10.1016/j.disc.2011.02.013.
  3. D. Chen and W. Wang. (2, 1)-total labelling of outerplanar graphs. Discrete Applied Mathematics, 155(18):2585–2593, 2007. https://doi.org/10.1016/j.dam.2007.07.016.
  4. M.-L. Chia, D. Kuo, J.-H. Yan, and S.-R. Yang. (p, q)-total labeling of complete graphs. Journal of Combinatorial Optimization, 25(4):543–561, 2013. https://doi.org/10.1007/s10878-012-9471-1.
  5. X. Deng, Z. Shao, H. Zhang, and W. Yang. The (d, 1)-total labelling of sierpinski-like graphs. Applied Mathematics and Computation, 361:484–492, 2019. https://doi.org/10.1016/j.amc.2019.05.050.
  6. L. Ferrarini, G. Mazzuoccolo, and V. Mkrtchyan. Normal 5-edge-colorings of a family of loupekine snarks. AKCE International Journal of Graphs and Combinatorics, 17(3):720–724, 2020. https://doi.org/10.1016/j.akcej.2019.12.014.
  7. C. Fiori, G. Mazzuoccolo, and B. Ruini. Computing the automorphic chromatic index of certain snarks. Results in Mathematics, 58:241–254, 2010. https://doi.org/10.1007/s00025-010-0051-3.
  8. J. A. Gallian. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 6(25):4–623, 2022.
  9. M. Ghebleh. The circular chromatic index of goldberg snarks. Discrete Mathematics, 307(24):3220–3225, 2007. https://doi.org/10.1016/j.disc.2007.03.047.
  10. M. K. Goldberg. Construction of class 2 graphs with maximum vertex degree 3. Journal of Combinatorial Theory, Series B, 31(3):282–291, 1981. https://doi.org/10.1016/0095-8956(81)90030-7.
  11. I. F. Gonçalves, S. Dantas, and D. Sasaki. On equitable total coloring of snarks. Procedia Computer Science, 195:334–342, 2021. https://doi.org/10.1016/j.procs.2021.11.041.
  12. J. R. Griggs and R. K. Yeh. Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595, 1992. https://doi.org/10.1137/0405048.
  13. F. Havet. (d, 1)-total labelling of graphs. Workshop on Graphs and Algorithms, Dijon, France, 2002.
  14. F. Havet and S. Thomassé. Complexity of (p, 1)-total labelling. Discrete Applied Mathematics, 157(13):2859–2870, 2009. https://doi.org/10.1016/j.dam.2009.03.021.
  15. F. Havet and M.-L. Yu. (d, 1)-Total Labelling of Graphs. PhD thesis, INRIA, 2002.
  16. F. Havet and M.-L. Yu. (p, 1)-total labelling of graphs. Discrete Mathematics, 308(4):496–513, 2008. https://doi.org/10.1016/j.disc.2007.03.034.
  17. R. Isaacs. Loupekine’s snarks: a bifamily of non-tait-colorable graphs. Journal of Combinatorial Theory, Series B, 1976.
  18. K.-W. Lih, D. D.-F. Liu, and W. Wang. On (d, 1)-total numbers of graphs. Discrete Mathematics, 309(12):3767–3773, 2009. https://doi.org/10.1016/j.disc.2008.10.008.
  19. D. Ma, H. Zhu, and J. He. λ-numbers of several classes of snarks. Journal of Combinatorial Optimization, 28(4):787–799, 2014. https://doi.org/10.1007/s10878-012-9589-1.
  20. M. Montassier and A. Raspaud. (d, 1)-total labeling of graphs with a given maximum average degree. Journal of Graph Theory, 51(2):93–109, 2006. https://doi.org/10.1002/jgt.20124.
  21. B. Niu and S. Liu. On (p, 1)-total labelling of nic-planar graphs. Bulletin of the Malaysian Mathematical Sciences Society, 44:4239–4250, 2021. https://doi.org/10.1007/s40840-021-01165-0.
  22. B. Niu and X. Zhang. On (p, 1)-total labelling of some 1-planar graphs. Discussiones Mathematicae Graph Theory, 41(2):531–558, 2021. http://dx.doi.org/10.7151/dmgt.2208.
  23. M. A. Palma, I. F. Gonçalves, D. Sasaki, and S. Dantas. On total coloring and equitable total coloring of infinite snark families. RAIRO-Operations Research, 57(5):2619–2637, 2023. https://doi.org/10.1051/ro/2023129.
  24. D. Sasaki, S. Dantas, C. M. de Figueiredo, and M. Preissmann. The hunting of a snark with total chromatic number 5. Discrete Applied Mathematics, 164:470–481, 2014. https://doi.org/10.1016/j.dam.2013.04.006.
  25. L. Sun and H. Cai. On (p, 1)-total labelling of special 1-planar graphs. Ars Combinatoria, 123:87–96, Oct. 2015.
  26. L. Sun and J.-L. Wu. On (p, 1)-total labelling of planar graphs. Journal of Combinatorial Optimization, 33:317–325, 2017. https://doi.org/10.1007/s10878-015-9958-7.
  27. C. Tong, S. Su, and Y. Yang. (d, 1)-total labelling of generalized Petersen graphs P(n,k). Ars Combinatoria, 158:11–17, Jan. 2024. https://doi.org/10.61091/ars158-02.
  28. C. Tong, S. Su, and Y. Yang. (d,1)-total labellings of regular nonbipartite graphs and an application to flower snarks. Ars Combinatoria, 158:11–17.
  29. W. Wang, J. Huang, D. Huang, and S. Haina. (2, 1)-total number of joins of paths and cycles. Taiwanese Journal of Mathematics, 16(2):605–619, 2012. https://doi.org/10.11650/twjm/1500406605.
  30. M. A. Whittlesey, J. P. Georges, and D. W. Mauro. On the λ-number of Qn and related graphs. SIAM Journal on Discrete Mathematics, 8(4):499–506, 1995. https://doi.org/10.1137/S0895480192242821.
  31. X. Zhang, G. Liu, and Y. Yu. On (p, 1)-total labelling of plane graphs with independent crossings. Filomat, 26(6):1091–1100, 2012.
Citation
Zhiqiang Gao, Chunling Tong, XingKuan Bai, Wenzheng An. \((d,1)\)-Total labellings of two infinite families of snarks[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 124. 291-301. https://doi.org/10.61091/jcmcc124-20.