We initiate to study a \(D\)-irregular labeling, which generalizes both non-inclusive and inclusive \(d\)-distance irregular labeling of graphs. Let \(G=(V(G),E(G))\) be a graph, \(D\) a set of distances, and \(k\) a positive integer. A mapping \(\varphi\) from \(V(G)\) to the set of positive integers \(\{1,2,\dots,k\}\) is called a \(D\)-irregular \(k\)-labeling of \(G\) if every two distinct vertices have distinct weights, where the weight of a vertex \(x\) is defined as the sum of labels of vertices whose distance from \(x\) belongs to \(D\). The least integer \(k\) for which \(G\) admits a \(D\)-irregular labeling is the \(D\)-irregularity strength of \(G\) and denoted by \(\mathrm{s}_D(G)\). In this paper, we establish several fundamental properties on \(D\)-irregularity strength for arbitrary graphs. We also determine this parameter exactly for families of graphs with small diameter or small maximum degree.
Throughout the paper, only undirected simple finite graphs are considered. For undefined terminology and notation, we follow [8]. Let \(G\) be a graph. We will denote by \(V(G)\) and \(E(G)\) the vertex and edge set of \(G\), respectively. The distance between two vertices \(x,y\in V(G)\) will be denoted by \(d(x,y)\).
Graph labeling has been an intriguing topic, extensively studied over the last six decades. To date, over \(350\) graph labelings techniques have been developed in over \(3600\) papers [11], one of which is a distance antimagic labeling, firstly established by Kamatchi and Arumugam [14]. A bijection \(\varphi:V(G)\rightarrow\{1,2,\dots,|V(G)|\}\) is said to be a distance antimagic labeling of a graph \(G\) if the vertex weights, given by \[wt(x)=\sum_{z\in N(x)}\varphi(z),\] are all distinct, where \(N(x)\), the open neighborhood of \(x\), is the set of all vertices adjacent to \(x\). A distance antimagic graph is a graph that has a distance antimagic labeling.
Simanjuntak et al. [16] introduced a more generalized concept, called a \(D\)-antimagic labeling, where \(D\) is a non-empty subset of the set \(\{0,1,\dots,\mathrm{diam}(G)\}\). Here, the difference is that the weight of a vertex \(x\) is now defined as \[wt(x)=\sum_{z\in N_D(x)}\varphi(z),\] where \(N_D(x)=\{z:d(x,z)\in D\}\) is the \(D\)-neighborhood of \(x\). A graph that admits a \(D\)-antimagic labeling is called \(D\)-antimagic. Notably, a \(\{1\}\)-antimagic graph is corresponds to a distance antimagic graph. Some graph families have been proved to be \(D\)-antimagic, among others, see [9,12,13,14,16,17,24].
Instead of looking at bijection type labelings, Chartrand et al. [7] considered an edge \(k\)-labeling \(\varphi:E(G)\rightarrow\{1,2,\dots,k\}\) of a graph \(G\), where distinct edges may receive an identical label, such that the vertex weights, \[wt(x)=\sum_{xy\in E(G)}\varphi(xy),\] are all distinct. They named such labelings irregular assignments and the irregularity strength, \(\mathrm{s}(G)\), is the minimum positive integer \(k\) such that \(G\) has an irregular assignment using labels not exceeding \(k\). This topic has gained significant interest, with numerous papers published; see [2,3,15] for some recent results.
Combining distance-based labelings and irregular assignments, Slamin [18] introduced a non-inclusive distance irregular \(k\)-labeling of a graph \(G\) as a mapping \(\varphi:V(G)\rightarrow\{1,2,\dots,k\}\) such that for every two distinct vertices \(x,y\in V(G)\) there is \(wt(x)\ne wt(y)\), where \[wt(x)=\sum_{z\in N(x)}\varphi(z),\] is the weight of a vertex \(x\). The non-inclusive distance irregularity strength, \(\mathrm{dis}(G)\), of \(G\) is the smallest integer \(k\) such that \(G\) has a non-inclusive distance irregular labeling. There are not many graphs whose non-inclusive distance irregularity strengths are known. Among those that are known include paths, complete graphs, cycles, wheels, fan and book graphs [5,18], disjoint union of paths, suns, helms and friendships [20].
Later on, Bača et al. [4] modified such a labeling and introduced an inclusive distance irregular labeling of graphs. In this case, the label of the vertex is also included in the computation of its vertex weight, while the non-inclusive is not. Furthermore, the two labelings were generalized by Bong et al. [6] to non-inclusive and inclusive \(d\)-distance irregular labelings, where \(d\) is an integer arbitrarily taken from \(1\) up to the diameter of the graph. A (non-)inclusive \(1\)-distance irregular labeling is also called a (non-)inclusive distance irregular labeling. For more information on these subjects one can see [19,21,22,23].
In this paper, we propose a new invariant, called a \(D\)-irregular labeling, which generalizes the previous labelings mentioned in [4,16,18]. This generalization is analogous to \(D\)-antimagic labelings by Simanjuntak et al. [16]. The formal definition is provided below.
Definition 1.1. Let \(G=(V(G),E(G))\) be a graph with diameter \(\mathrm{diam}(G)\). For a non-empty set of distances \(D\subseteq\{0,1,\dots,\mathrm{diam}(G)\}\) and a positive integer \(k\), a function \(\varphi:V(G)\rightarrow\{1,2,\dots,k\}\) is called a \(D\)-irregular \(k\)-labeling of \(G\) if \(wt(x)\ne wt(y)\) for every two distinct vertices \(x,y\in V(G)\), where the weight of a vertex \(x\) is defined as \[wt(x)=\sum_{z\in N_D(x)}\varphi(z).\]
We set \(wt(x)=0\) if \(N_D(x)=\emptyset\). The \(D\)-irregularity strength of \(G\), denoted by \(\mathrm{s}_D(G)\), is the minimum \(k\) such that \(G\) admits a \(D\)-irregular labeling. If such an integer \(k\) does not exist then we define \(\mathrm{s}_D(G)=\infty\).
In a case when \(G\) is disconnected, we have that \(\mathrm{diam}(G)=\infty\), and \(D\subseteq\{0,1,\dots\}\). Suppose that \(G_1,G_2,\dots,G_m\), \(m\geqslant 2\), be the components of \(G\),\(\max_{1\leqslant i\leqslant m}\mathrm{diam}(G_i)=\partial\), and \(D'\subseteq D\cap\{\partial+1,\partial+2,\dots\}\). Then \(\mathrm{s}_D(G)=\mathrm{s}_{D-D'}(G)\). Moreover, from Definition 1.1, it follows that
A \(\{1\}\)-irregular labeling is a non-inclusive distance irregular labeling.
A \(\{0,1\}\)-irregular labeling is an inclusive distance irregular labeling.
For \(d\in\{1,2,\dots,\mathrm{diam}(G)\}\), a \(\{1,2,\dots,d\}\)-irregular labeling is a non-inclusive \(d\)-distance irregular labeling.
For \(d\in\{1,2,\dots,\mathrm{diam}(G)\}\), a \(\{0,1,\dots,d\}\)-irregular labeling is an inclusive \(d\)-distance irregular labeling.
The rest of the paper is organized as follows. In Section 2, we present fundamental properties of \(D\)-irregularity strength for arbitrary graphs. In Section 3, we compute the exact values on this parameter for certain graphs with small diameter. Section 4 addresses graphs with small maximum degree. Finally, Section 5 presents concluding remarks.
We start with the following theorem which provides the necessary and sufficient conditions for a graph to possess finite \(D\)-irregularity strength.
Theorem 2.1. Let \(G\) be a graph. Then \(\mathrm{s}_D(G)=\infty\) if and only if there exist two distinct vertices \(x,y\in V(G)\) such that \(N_D(x)=N_D(y)\). Moreover, if \(\mathrm{s}_D(G)<\infty\) then \(\mathrm{s}_D(G)\leqslant 2^{|V(G)|-1}\).
Proof. Let \(x,y\) be two vertices of \(G\) with \(N_D(x)=N_D(y)\). Then, in any vertex labeling \(\varphi\) of \(G\), \[wt(x)=\sum_{z\in N_D(x)}\varphi(z)=\sum_{z\in N_D(y)}\varphi(z)=wt(y),\] meaning that \(\varphi\) can not be \(D\)-irregular.
Now suppose that \(N_D(x)\ne N_D(y)\) for every two distinct vertices \(x,y\in V(G)\). Let us denote the vertices of \(G\) arbitrarily by the symbols \(x_1,x_2,\dots,x_{|V(G)|}\). Define a vertex \((2^{|V(G)|-1})\)-labeling \(\varphi\) of \(G\) as follows: \[\varphi(x_i)=2^{i-1}\quad\text{for }i=1,2,\dots,|V(G)|.\] We define a labeling \(\beta\) such that \[\beta_{ij}= \begin{cases} 1&\text{if }x_i\in N_D(x_j),\\ 0&\text{if }x_i\not\in N_D(x_j), \end{cases}\] where \(i=1,2,\dots,|V(G)|\) and \(j=1,2,\dots,|V(G)|\). Then, \[\label{EQU:sum} wt(x_j)=\sum_{x_i\in N_D(x_j)}\varphi(x_i)=\sum_{i:\text{ }x_i\in N_D(x_j)}2^{i-1}=\sum_{i=1}^{|V(G)|}\beta_{ij}2^{i-1}. \tag{1}\]
To prove that all the vertex weights are distinct, it suffices to show that the sums \(\sum_{i=1}^{|V(G)|}\beta_{ij}2^{i-1}\) are all distinct for \(j=1,2,\dots,|V(G)|\). However, this is evident if we consider that the ordered \(|V(G)|\)-tuple \((\beta_{1j},\beta_{2j},\dots,\beta_{|V(G)|j})\) corresponds to the binary code representation of the sum (1). Because \(N_D(x)\ne N_D(y)\) for every two distinct vertices \(x,y\in V(G)\) we can get that the \(|V(G)|\)-tuples are distinct for distinct vertices. Hence \(\mathrm{s}_D(G)\leqslant 2^{|V(G)|-1}\). ◻
In a non-trivial graph \(G\), it is evident that if \(D=\{0,1,\dots,\mathrm{diam}(G)\}\) then \(N_D(x)=V(G)=N_D(y)\) for any two vertices \(x,y\in V(G)\), and so by Theorem 2.1 \(G\) has no \(D\)-irregular labeling. Hence, the next corollary holds.
Corollary 2.2. . Let \(G\) be a non-trivial graph. Then \(\mathrm{s}_{\{0,1,\dots,\mathrm{diam}(G)\}}(G)=\infty\).
For a graph \(G\) and a set of distances \(D\), the complement of \(D\), denoted by \(D^c\), is a set in which \(D\cup D^c=\{0,1,\dots,\mathrm{diam}(G)\}\) and \(D\cap D^c=\emptyset\). In the next theorem, we give a relationship between \(D\)-irregularity strength and \(D^c\)-irregularity strength of graphs.
Theorem 2.3. Let \(G\) be a non-empty graph. Then
\(\mathrm{s}_D(G)=\infty\) if and only if \(\mathrm{s}_{D^c}(G)=\infty\).
If \(G\) is connected and \(\mathrm{s}_D(G)<\infty\) then \(\mathrm{s}_{D^c}(G)=\mathrm{s}_D(G)\).
Let \(G\) be a disconnected graph with components \(G_1,G_2,\dots,G_m\) for \(m\geqslant 2\), and \(\mathrm{s}_D(G)<\infty\). If there exists a \(D\)-irregular \(\mathrm{s}_D(G)\)-labeling \(\varphi\) of \(G\) with the property that \(wt(x)-wt(y)\ne\sum_{z\in V(G_i)}\varphi(z)-\sum_{z\in V(G_j)}\varphi(z)\) for every two distinct vertices \(x\in V(G_i)\) and \(y\in V(G_j)\), \(i\ne j\), then \(\mathrm{s}_{D^c}(G)\leqslant\mathrm{s}_D(G)\).
Proof. (a) If \(\mathrm{s}_D(G)=\infty\) then by Theorem 2.1 there exist two distinct vertices \(x,y\in V(G)\) such that \(N_D(x)=N_D(y)\). If \(G\) is connected then \[\begin{aligned} N_{D^c}(x)&=N_{\{0,1,\dots,\mathrm{diam}(G)\}-D}(x)\\ &=V(G)-N_D(x)=V(G)-N_D(y)=N_{\{0,1,\dots,\mathrm{diam}(G)\}-D}(y)=N_{D^c}(y), \end{aligned}\] and so \(\mathrm{s}_{D^c}(G)=\infty\) by Theorem 2.1.
Next, let \(G\) be disconnected with components \(G_1,G_2,\dots,G_m\) for some \(m\geqslant 2\). If \(x,y\in V(G_i)\) for some \(i\), then \[\begin{aligned} N_{D^c}(x)&=N_{\{0,1,\dots\}-D}(x)=N_{(\{0,1,\dots,\mathrm{diam}(G_i)\}-D)\cup\{\mathrm{diam}(G_i)+1,\mathrm{diam}(G_i)+2,\dots\}}(x)\\ &=N_{\{0,1,\dots,\mathrm{diam}(G_i)\}-D}(x)=V(G_i)-N_D(x)=V(G_i)-N_D(y)\\ &=N_{\{0,1,\dots,\mathrm{diam}(G_i)\}-D}(y)=N_{(\{0,1,\dots,\mathrm{diam}(G_i)\}-D)\cup\{\mathrm{diam}(G_i)+1,\mathrm{diam}(G_i)+2,\dots\}}(y)\\ &=N_{\{0,1,\dots\}-D}(y)=N_{D^c}(y), \end{aligned}\] thus \(\mathrm{s}_{D^c}(G)=\infty\) by Theorem 2.1. If \(x\in V(G_i)\) and \(y\in V(G_j)\) with \(\mathrm{diam}(G_i)\geqslant\mathrm{diam}(G_j)\) for \(i\ne j\), then \(N_D(x)=N_D(y)=\emptyset\), and so \(D\subseteq\{\mathrm{diam}(G_i)+1,\mathrm{diam}(G_i)+2,\dots\}\). As \(G\) is a non-empty graph, we may assume that \(G_i\) contains at least two vertices. Indeed, for every two distinct vertices \(x,z\in V(G_i)\), \(N_{D^c}(x)=N_{D^c}(z)=N_{\{0,1,\dots\}-D}(z)=N_{(\{0,1,\dots,\mathrm{diam}(G_i)\}-D)\cup\{\mathrm{diam}(G_i)+1,\mathrm{diam}(G_i)+2,\dots\}}(z)=N_{\{0,1,\dots,\mathrm{diam}(G_i)\}}(z)=V(G_i)\), hence \(\mathrm{s}_{D^c}(G)=\infty\) by Theorem 2.1.
Conversely, if \(\mathrm{s}_{D^c}(G)=\infty\), similar reasoning shows that \(\mathrm{s}_{D}(G)=\infty\).
(b) Let \(G\) be connected and \(\mathrm{s}_D(G)<\infty\). Let \(\varphi\) be a \(D\)-irregular \(\mathrm{s}_D(G)\)-labeling of \(G\). We define a new vertex labeling \(\varphi'\) of \(G\) in such a way that \[\varphi'(x)=\varphi(x)\quad\text{for }x\in V(G).\]
We show that \(\varphi'\) is a \(D^c\)-irregular \(\mathrm{s}_D(G)\)-labeling of \(G\).
Evidently \(\varphi'(x)\leqslant\mathrm{s}_D(G)\) for all \(x\in V(G)\). For the vertex weights under the labeling \(\varphi'\) we have \[wt(x)=\sum_{z\in N_{D^c}(x)}\varphi'(z)=\sum_{z\in N_{\{0,1,\dots,\mathrm{diam}(G)\}-D}(x)}\varphi'(z)=\sum_{z\in V(G_i)}\varphi(z)-\sum_{z\in N_D(x)}\varphi(z).\]
Note that the sums \(\sum_{z\in N_D(x)}\varphi(z)\) are distinct for each \(x\in V(G)\) since \(\varphi\) is \(D\)-irregular. This implies that \(wt(x)\ne wt(y)\) for every two distinct vertices \(x,y\in V(G)\), and so \(\mathrm{s}_{D^c}(G)\leqslant\mathrm{s}_D(G)\).
Since \(\mathrm{s}_D(G)<\infty\) we have \(\mathrm{s}_{D^c}(G)<\infty\) according to (1). Then, by similar arguments, we can prove that \(\mathrm{s}_{D}(G)\leqslant\mathrm{s}_{D^c}(G)\). Therefore \(\mathrm{s}_{D^c}(G)=\mathrm{s}_{D}(G)\).
(c) Let \(G\) be a disconnected graph with components \(G_1,G_2,\dots,G_m\) for \(m\geqslant 2\), and \(\mathrm{s}_D(G)<\infty\). Assume \(\varphi\) be a \(D\)-irregular \(\mathrm{s}_D(G)\)-labeling of \(G\) satisfying the stated condition. Define a new vertex labeling \(\varphi'\) of \(G\) such that \[\varphi'(x)=\varphi(x)\quad\text{for }x\in V(G).\]
We shall show that \(\varphi'\) is a \(D^c\)-irregular \(\mathrm{s}_D(G)\)-labeling of \(G\).
Clearly \(\varphi'(x)\leqslant\mathrm{s}_D(G)\) for all \(x\in V(G)\). Let us consider the weight of any vertex \(x\) in the component \(G_i\), \(i=1,2,\dots,m\), under the labeling \(\varphi'\). We have \[\begin{aligned} wt(x)&=\sum_{z\in N_{D^c}(x)}\varphi'(z)=\sum_{z\in N_{\{0,1,\dots\}-D}(x)}\varphi'(z)\\ &=\sum_{z\in N_{(\{0,1,\dots,\mathrm{diam}(G_i)\}-D)\cup\{\mathrm{diam}(G_i)+1,\mathrm{diam}(G_i)+2,\dots\}}(x)}\varphi'(z)\\ &=\sum_{z\in N_{\{0,1,\dots,\mathrm{diam}(G_i)\}-D}(x)}\varphi'(z)\\ &=\sum_{z\in V(G_i)}\varphi(z)-\sum_{z\in N_D(x)}\varphi(z). \end{aligned}\]
Consider any two distinct vertices \(x,y\in V(G)\). Evidently if \(x\) and \(y\) are in the same component then \(wt(x)\ne wt(y)\) since \(\sum_{z\in N_D(x)}\varphi(z)\ne\sum_{z\in N_D(y)}\varphi(z)\). Now, suppose that \(x\) and \(y\) are in the different components, say \(x\in V(G_i)\) and \(y\in V(G_j)\) for \(i\ne j\). By the property in (3), it follows that \(wt(x)\ne wt(y)\). So all the vertex weights are distinct, and hence \(\mathrm{s}_{D^c}(G)\leqslant\mathrm{s}_D(G)\). ◻
It is evident that every \(D\)-antimagic labeling is also a \(D\)-irregular labeling. Consequently, we derive the following property, which provides a better upper bound for \(\mathrm{s}_D(G)\) in a case that \(G\) is \(D\)-antimagic.
Proposition 2.4. Let \(G\) be a \(D\)-antimagic graph on \(n\) vertices. Then \(\mathrm{s}_D(G)\leqslant n\).
The next proposition, which is straightforward, shows that the upper bound in Proposition 2.4 is sharp.
Proposition 2.5. Let \(G\) be a graph on \(n\) vertices. If one of the following conditions holds:
\(G\) is connected and \(D\in\{\{0\},\{1,2,\dots,\mathrm{diam}(G)\}\}\),
\(G\cong mK_2\), \(m\geqslant 2\), and \(D\in\{\{0\},\{1\}\}\), or
\(G\) is disconnected, \(G\not\cong mK_2\), \(m\geqslant 2\), and \(D=\{0\}\),
then \(G\) is \(D\)-antimagic and \(s_D(G)=n\).
In the next theorem, we provide lower bounds for \(D\)-irregularity strength of arbitrary graphs. For a vertex \(x\) in a graph \(G\), the \(D\)-degree, \(d_D(x)\) of \(x\) is the cardinality of the set \(N_D(x)\).
Theorem 2.6. Let \(G\) be a graph with \(\mathrm{s}_D(G)<\infty\). Let \(\delta_{D}(G)\) and \(\Delta_{D}(G)\) be the minimum and the maximum \(D\)-degree of vertices of \(G\), respectively. Let \(n_{D,i}\) be the number of vertices in \(G\) with \(D\)-degree \(i\) for \(i=\delta_D(G),\delta_D(G)+1,\dots,\Delta_D(G)\). Then, \[\mathrm{s}_D(G)\geqslant\max_{\delta_D(G)\leqslant i\leqslant\Delta_D(G)}\left\{\left\lceil\frac{\delta_D(G)+\sum_{j=\delta_D(G)}^{i}n_{D,j}-1}{i}\right\rceil\right\}.\]
Proof. For some \(t\), let \[\left\lceil\frac{\delta_D(G)+\sum_{j=\delta_D(G)}^{t}n_{D,j}-1}{t}\right\rceil=\max_{\delta_D(G)\leqslant i\leqslant\Delta_D(G)}\left\{\left\lceil\frac{\delta_D(G)+\sum_{j=\delta_D(G)}^{i}n_{D,j}-1}{i}\right\rceil\right\}.\] In any \(D\)-irregular labeling of a graph \(G\), the smallest weight of vertices with \(D\)-degrees \(\delta_D(G),\delta_D(G)+1,\dots,t\) is at least \(\delta_D(G)\), and the largest among them must be at least \(\delta_D(G)+\sum_{j=\delta_D(G)}^{t}n_{D,j}-1\). Such largest weight is obtained from the sum of at most \(t\) labels. Therefore \[\begin{aligned} \mathrm{s}_D(G)&\geqslant\left\lceil\frac{\delta_D(G)+\sum_{j=\delta_D(G)}^{t}n_{D,j}-1}{t}\right\rceil=\max_{\delta_D(G)\leqslant i\leqslant\Delta_D(G)}\left\{\left\lceil\frac{\delta_D(G)+\sum_{j=\delta_D(G)}^{i}n_{D,j}-1}{i}\right\rceil\right\}. \end{aligned}\] ◻
Notice that if \(D=\{1\}\), \(D=\{0,1\}\), and \(D=\{0,1,\dots,d\}\), \(1\leqslant d\leqslant\mathrm{diam}(G)\), then we acquire the lower bounds for \(\mathrm{s}_D(G)\) which were proved in [21, Theorem 2.1], [19, Theorem 2], and [23, Lemma 2.1], respectively.
The next two theorems demonstrate key properties that will be instrumental in determining the \(D\)-irregularity strength of a graph.
Theorem 2.7. Let \(G\) be a graph with \(\mathrm{s}_D(G)<\infty\). Let \(x,y\) be two distinct vertices of \(G\) such that \(N_D(x)-\{y\}=N_D(y)-\{x\}\). Then \(x\) and \(y\) must receive distinct labels in any \(D\)-irregular labeling of \(G\). Furthermore, if \(G\) is connected then \(x\) and \(y\) must receive distinct labels in any \(D^c\)-irregular labeling of \(G\).
Proof. Let \(x,y\) be two distinct vertices of \(G\) with \(N_D(x)-\{y\}=N_D(y)-\{x\}\). As \(\mathrm{s}_D(G)<\infty\), \(x\in N_D(y)\) and \(y\in N_D(x)\). Next, in any \(D\)-irregular labeling \(\varphi\) of \(G\), \[wt(x)=\sum_{z\in N_D(x)}\varphi(z)=\varphi(y)+\sum_{z\in N_D(x)-\{y\}}\varphi(z),\] and \[wt(y)=\sum_{z\in N_D(y)}\varphi(z)=\varphi(x)+\sum_{z\in N_D(y)-\{x\}}\varphi(z).\]
Since \(wt(x)\ne wt(y)\) and \(\sum_{z\in N_D(x)-\{y\}}\varphi(z)=\sum_{z\in N_D(y)-\{x\}}\varphi(z)\) then \(\varphi(x)\ne\varphi(y)\).
Now let \(G\) be connected. Then, in any \(D^c\)-irregular labeling \(\varphi\) of \(G\), \[\begin{aligned} wt(x)&=\sum_{z\in N_{D^c}(x)}\varphi(z)=\sum_{z\in N_{\{0,1,\dots,\mathrm{diam}(G)\}-D}(x)}\varphi(z)=\sum_{z\in V(G)}\varphi(z)-\sum_{z\in N_D(x)}\varphi(z)\\ &=\sum_{z\in V(G)}\varphi(z)-\varphi(y)-\sum_{z\in N_D(x)-\{y\}}\varphi(z), \end{aligned}\] and \[\begin{aligned} wt(y)&=\sum_{z\in N_{D^c}(y)}\varphi(z)=\sum_{z\in N_{\{0,1,\dots,\mathrm{diam}(G)\}-D}(y)}\varphi(z)=\sum_{z\in V(G)}\varphi(z)-\sum_{z\in N_D(y)}\varphi(z)\\ &=\sum_{z\in V(G)}\varphi(z)-\varphi(x)-\sum_{z\in N_D(y)-\{x\}}\varphi(z). \end{aligned}\]
Since \(wt(x)\ne wt(y)\) and \(\sum_{z\in N_D(x)-\{y\}}\varphi(z)=\sum_{z\in N_D(y)-\{x\}}\varphi(z)\) then \(\varphi(x)\ne\varphi(y)\). ◻
Theorem 2.8. Let \(G\) be a graph, \(D=D'\cup D''\), \(D'\cap D''=\emptyset\), and \(\mathrm{s}_D(G)<\infty\). Let \(x,y\) be two distinct vertices of \(G\) such that \(x\not\in N_D(y)\) and \(y\not\in N_D(x)\). If \(N_{D'}(x)=N_{D'}(y)\), \(N_{D''}(x)\ne N_{D''}(y)\) and \(|N_{D''}(x)|=|N_{D''}(y)|=1\) then vertices in \(N_{D''}(x)\) and \(N_{D''}(y)\) must receive distinct labels in any \(D\)-irregular labeling of \(G\).
Proof. Let \(x,y\) be two distinct vertices of \(G\) with \(x\not\in N_D(y)\) and \(y\not\in N_D(x)\) such that \(N_{D'}(x)=N_{D'}(y)\), \(N_{D''}(x)\ne N_{D''}(y)\) and \(|N_{D''}(x)|=|N_{D''}(y)|=1\). Let \(N_{D''}(x)=\{x'\}\) and \(N_{D''}(y)=\{y'\}\), where \(x'\ne y'\). Then, in any \(D\)-irregular labeling \(\varphi\) of \(G\), \[\begin{aligned} wt(x)&=\sum_{z\in N_D(x)}\varphi(z)=\sum_{z\in N_{D'\cup D''}(x)}\varphi(z)=\sum_{z\in N_{D'}(x)}\varphi(z)+\sum_{z\in N_{D''}(x)}\varphi(z)\\ &=\sum_{z\in N_{D'}(x)}\varphi(z)+\varphi(x'), \end{aligned}\] and \[\begin{aligned} wt(y)&=\sum_{z\in N_D(y)}\varphi(z)=\sum_{z\in N_{D'\cup D''}(y)}\varphi(z)=\sum_{z\in N_{D'}(y)}\varphi(z)+\sum_{z\in N_{D''}(y)}\varphi(z)\\ &=\sum_{z\in N_{D'}(y)}\varphi(z)+\varphi(y'). \end{aligned}\]
Since \(wt(x)\ne wt(y)\) and \(\sum_{z\in N_{D'}(x)}\varphi(z)=\sum_{z\in N_{D'}(y)}\varphi(z)\) then \(\varphi(x')\ne\varphi(y')\). ◻
Notice that when \(D=\{1\}\), Theorem 2.7 yields the result mentioned in [18, Observation 2], and also when \(D=\{0,1\}\), \(D'=\{1\}\), and \(D''=\{0\}\), Theorem 2.8 provides the property proved in [4, Lemma 3.1].
In [16], Simanjuntak et al. defined a distance-\(D\) graph of a graph \(G\), denoted by \(G_D\), as a simple graph with the same vertices as \(G\), where two vertices are adjacent if their distance in \(G\) is an element of \(D\). Note that, since \(G_D\) is a simple graph, any loops that would arise when \(0\in D\) are excluded from the graph.
Theorem 2.9. Let \(G\) be a graph.
If \(D\) does not contain \(0\) then \(\mathrm{s}_{\{1\}}(G_D)=\mathrm{s}_D(G)\).
If \(D\) contains \(0\) then \(\mathrm{s}_{\{0,1\}}(G_D)=\mathrm{s}_D(G)\).
Proof. Let \(\varphi\) be a \(D\)-irregular \(s_D(G)\)-labeling of a graph \(G\). We define a vertex labeling \(\varphi'\) of \(G_D\) in the following way. \[\varphi'(x')=\varphi(x),\] for any vertex \(x'\in V(G_D)\) corresponding to a vertex \(x\in V(G)\).
If \(0\not\in D\), then we have \[\sum_{y\in N(x')}\varphi'(y)=\sum_{y\in N_D(x)}\varphi(y),\] which implies that \(\mathrm{s}_{\{1\}}(G_D)\leqslant\mathrm{s}_D(G)\). Using similar arguments, we can also show that \(\mathrm{s}_D(G)\leqslant\mathrm{s}_{\{1\}}(G_D)\), so \(\mathrm{s}_{\{1\}}(G_D)=\mathrm{s}_D(G)\). This proves (1).
Furthermore, if \(0\in D\) then \[\varphi'(x)+\sum_{y\in N(x')}\varphi'(y)=\sum_{y\in N_D(x)}\varphi(y),\] which leads to \(\mathrm{s}_{\{0,1\}}(G_D)\leqslant\mathrm{s}_D(G)\). Again, using similar reasoning, we can demonstrate that \(\mathrm{s}_D(G)\leqslant\mathrm{s}_{\{0,1\}}(G_D)\), thus \(\mathrm{s}_{\{0,1\}}(G_D)=\mathrm{s}_D(G)\). This completes the proof of (2). ◻
This section showcases the \(D\)-irregularity strength for families of graphs with diameter at most three, including complete graphs, the join graph \(G+K_1\), complete bipartite graphs, and double stars, for all possible sets \(D\).
A complete graph \(K_n\) is the graph with \(n\) vertices in which any two of them are joined by an edge. Evidently, the graph \(K_1\) is the only graph of diameter zero, and the graph \(K_n\), \(n\geqslant 2\), is the only graph with diameter one.
A complete bipartite graph \(K_{m,n}\) is the graph whose vertices can be partitioned into two subsets \(X\) and \(Y\) with \(|X|=m\) and \(|Y|=n\), such that \(xy\) is an edge if and only if \(x\in X\) and \(y\in Y\). The graph \(K_{m,n}\), \(1\leqslant m\leqslant n\), \((m,n)\ne (1,1)\), has diameter two. The complete bipartite graph \(K_{1,n}\) is called a star, the only tree with diameter two.
The join product between two given graphs \(G\) and \(H\), denoted by \(G+H\), is the graph obtained from \(G\) and \(H\) by joining an edge from every vertex of \(G\) to every vertex of \(H\). The graph \(G+H\) has diameter one or two, with diameter one if and only if \(G\) and \(H\) are complete graphs. Therefore, the graph \(G+K_1\) has diameter two if and only if \(G\) is not a complete graph.
A double star \(S_{m,n}\) is the graph obtained from two stars \(K_{1,m}\) and \(K_{1,n}\) by connecting the two vertices of degrees \(m\) and \(n\) in \(K_{1,m}\) and \(K_{1,n}\), respectively. The graph \(S_{m,n}\), \(1\leqslant m\leqslant n\), is the only tree with diameter three.
We first examine complete graphs. It is evident that \(\mathrm{s}_{D}(K_1)=1\). We shall show that \(K_1\) is the only graph with \(D\)-irregularity strength one. Beforehand, let us prove in the next proposition a generalization of the well-known property that a simple graph on \(n\geqslant 2\) vertices whose all the vertex degrees are distinct does not exist.
Theorem 3.1. There is no simple graph on \(n\geqslant 2\) vertices whose vertex \(D\)-degrees are all distinct.
Proof. Assume that such a graph \(G\) exists. Note that the \(D\)-degree of a vertex is at least \(0\) and at most \(n\). Thus, \(n\) numbers in the set \(\{0,1,\dots,n\}\) have to be the \(D\)-degree of vertices of \(G\).
We will show that \(n\) cannot be a vertex \(D\)-degree. Assume otherwise, that \(d_D(x)=n\) for some vertex \(x\in V(G)\). This means that \(N_D(x)=V(G)\), which forces \(G\) to be connected and \(D=\{0,1,\dots,\mathrm{diam}(G)\}\). But then, this implies that \(N_D(y)=V(G)\) for any vertex \(y\ne x\in V(G)\), and so \(N_D(x)=N_D(y)\), a contradiction. Therefore the vertex \(D\)-degrees of \(G\) must be \(0,1,\dots,n-1\).
Consider two distinct vertices \(x,y\in V(G)\) with \(d_D(x)=0\) and \(d_D(y)=n-1\). Since \(d_D(x)=0\), we get \(0\not\in D\). This implies that \(N_D(y)=V(G)-\{y\}\), and so \(x\in N_D(y)\). However, this is impossible since \(d_D(x)=0\). Hence, the statement holds. ◻
From Proposition 3.1 it follows that for any graph \(G\) of order \(n\geqslant 2\), labeling all vertices of \(G\) with \(1\) will always result in at least two vertices with the same weight. This brings us to the characterization of graphs with \(D\)-irregularity strength one.
For \(n\geqslant 2\), the \(D\)-irregularity strength of the complete graph \(K_n\) which can be directly derived from Proposition 2.5 and Corollary 2.2, is presented in the following theorem. Note that the cases when \(D=\{1\}\) and \(D=\{0,1\}\) were also proved in [18] and [4], respectively.
Theorem 3.4 ([4,18]). Let \(K_n\) be a complete graph for \(n\geqslant 2\). Then \[\mathrm{s}_D(K_n)= \begin{cases} n&\text{if }D\in\{\{0\},\{1\}\},\\ \infty&\text{if }D=\{0,1\}. \end{cases}\]
Next, we deal with the join graph \(G+K_1\). To begin, let us restate the results on \(\mathrm{s}_D(G+K_1)\) for \(D=\{1\}\) and \(D=\{0,1\}\).
Theorem 3.5. ([22]). Let \(G\) be a graph. If \(\mathrm{s}_{\{1\}}(G)=\infty\) then \(\mathrm{s}_{\{1\}}(G+K_1)=\infty\). Moreover, if \(\mathrm{s}_{\{1\}}(G)<\infty\) then \[\mathrm{s}_{\{1\}}(G+K_1)= \begin{cases} \mathrm{s}_{\{1\}}(G)&\text{if there exists a }\{1\}\text{-irregular }\mathrm{s}_{\{1\}}(G)\text{-labeling }\varphi\text{ of }G\\ &\text{such that }\sum_{x\in V(G)}\varphi(x)>\max\{wt(x):x\in V(G)\}+1,\\ \mathrm{s}_{\{1\}}(G)+1&\text{otherwise}. \end{cases}\]
Theorem 3.6 ([4]). Let \(G\) be a graph with maximum degree \(\Delta(G)\). Then \[\mathrm{s}_{\{0,1\}}(G+K_1)= \begin{cases} \mathrm{s}_{\{0,1\}}(G)&\text{if }\Delta(G)<|V(G)|-1,\\ \infty&\text{if }\Delta(G)=|V(G)|-1. \end{cases}\]
Corollary 2.2, Proposition 2.5, and Theorems 2.3, 3.5 and 3.6 allow us to completely obtained exact values on \(D\)-irregularity strength for the graph \(G+K_1\).
If \(D\in\{\{0\},\{1,2\}\}\) then \(\mathrm{s}_D(G+K_1)=n+1\).
If one of the following conditions is satisfied:
\(D\in\{\{2\},\{0,1\}\}\) and \(\Delta(G)<|V(G)|-1\), or
\(D\in\{\{1\},\{0,2\}\}\) and there exists a \(\{1\}\)-irregular \(\mathrm{s}_{\{1\}}(G)\)-labeling \(\varphi\) of \(G\) such that \(\sum_{x\in V(G)}\varphi(x)>\max\{wt(x):x\in V(G)\}+1\),
then \(\mathrm{s}_D(G+K_1)=\mathrm{s}_D(G)\).
If \(D\in\{\{1\},\{0,2\}\}\) and \(\sum_{x\in V(G)}\varphi(x)=\max\{wt(x):x\in V(G)\}+1\) for every \(\{1\}\)-irregular \(\mathrm{s}_{\{1\}}(G)\)-labeling \(\varphi\) of \(G\), then \(\mathrm{s}_D(G+K_1)=\mathrm{s}_D(G)+1\).
If one of the following conditions is satisfied:
\(D\in\{\{1\},\{0,2\}\}\) and \(\mathrm{s}_{D}(G)=\infty\),
\(D\in\{\{2\},\{0,1\}\}\) and \(\Delta(G)=|V(G)|-1\), or
\(D=\{0,1,2\}\),
then \(\mathrm{s}_D(G+K_1)=\infty\).
Now, consider the complete bipartite graph \(K_{m,n}\) for \(1\leqslant m\leqslant n\), \((m,n)\ne (1,1)\). By Proposition 2.5, it is clear that \(\mathrm{s}_{\{0\}}(K_{m,n})=\mathrm{s}_{\{1,2\}}(K_{m,n})=m+n\). From [4, Theorem 3.1] and Theorem 2.3, we know that \(\mathrm{s}_{\{0,1\}}(K_{m,n})=\mathrm{s}_{\{2\}}(K_{m,n})=n\) when \(m<n\), and \(\mathrm{s}_{\{0,1\}}(K_{m,n})=\mathrm{s}_{\{2\}}(K_{m,n})=n+2\) when \(m=n\geqslant 2\). Moreover, \(\mathrm{s}_D(K_{m,n})=\infty\) whenever \(D\in\{\{1\},\{0,2\},\{0,1,2\}\}\), which follows immediately from [18, Observation 1], Theorem 2.3 and Corollary 2.2. Thus, we arrive at the following theorem.
Corollary 3.9. Let \(K_{1,n}\) be a star for \(n\geqslant 2\). Then \[\mathrm{s}_D(K_{1,n})= \begin{cases} n+1&\text{if }D\in\{\{0\},\{1,2\}\},\\ n&\text{if }D\in\{\{2\},\{0,1\}\},\\ \infty&\text{if }D\in\{\{1\},\{0,2\},\{0,1,2\}\}. \end{cases}\]
We now focus on the double star. Let us denote the vertex and edge set of the double star \(S_{m,n}\) respectively by \(V(S_{m,n})=\{x,x_i:i=1,2,\dots,m\}\cup\{y,y_j:j=1,2,\dots,n\}\) and \(E(S_{m,n})=\{xy\}\cup\{xx_i:i=1,2,\dots,m\}\cup\{yy_j:j=1,2,\dots,n\}\).
Theorem 3.10 ([6]) Let \(S_{m,n}\) be a double star for \(1\leqslant m\leqslant n\). Then \[\mathrm{s}_{\{0,1\}}(S_{m,n})= \begin{cases} n&\text{if }m<n,\\ n+1&\text{otherwise}. \end{cases}\]
Lemma 3.11. If \(D\in\{\{1\},\{0,2,3\}\}\) then \(\mathrm{s}_D(S_{1,1})=2\).
Proof. Obviously, \(\mathrm{s}_{\{1\}}(S_{1,1})=2\). Combining this with Theorem 2.3, \(\mathrm{s}_{\{0,2,3\}}(S_{1,1})=2\). ◻
Lemma 3.12. Let \(S_{m,n}\) be a double star for \(1\leqslant m<n\). If \(D\in\{\{0,1\},\{0,3\},\{1,2\},\{2,3\}\}\) then \(\mathrm{s}_D(S_{m,n})=n\).
Proof. From Theorems 2.3 and 3.10, we get \(\mathrm{s}_{\{0,1\}}(S_{m,n})=\mathrm{s}_{\{2,3\}}(S_{m,n})=n\). Let \(D=\{0,3\}\). By Theorem 2.8, \(y_i\) and \(y_j\), \(i\ne j\), must receive distinct labels, thus \(\mathrm{s}_{\{0,3\}}(S_{m,n})\geqslant n\). Define a labeling \(\varphi:V(S_{m,n})\rightarrow\{1,2,\dots,n\}\) such that \[\begin{aligned} \varphi(x)&=1,\\ \varphi(y)&=2,\\ \varphi(x_i)&=i\quad\text{for }i=1,2,\dots,m,\\ \varphi(y_j)&=j\quad\text{for }j=1,2,\dots,n. \end{aligned}\]
It is easy to see that all vertex labels are at most \(n\). For the vertex weights we have \[\begin{aligned} wt(x)&=1,\\ wt(y)&=2,\\ wt(x_i)&=\tfrac{n(n+1)}{2}+i\quad\text{for }i=1,2,\dots,m,\\ wt(y_j)&=\tfrac{m(m+1)}{2}+j\quad\text{for }j=1,2,\dots,n. \end{aligned}\]
As \(m<n\), we get that \(\tfrac{m(m+1)}{2}+n<\tfrac{n(n+1)}{2}+1\), which implies that the vertex weights are all distinct. Therefore \(\mathrm{s}_{\{0,3\}}(S_{m,n})=n\). By combining this with Theorem 2.3 we also have \(\mathrm{s}_{\{1,2\}}(S_{m,n})=n\). ◻
Lemma 3.13. Let \(S_{m,n}\) be a double star for \(1\leqslant m\leqslant n\). If one of the following conditions holds:
\(D\in\{\{2\},\{0,1,3\}\}\) and \(m<n\), or
\(D\in\{\{0,1\},\{2,3\}\}\) and \(m=n\),
then \(\mathrm{s}_D(S_{m,n})=n+1\).
Proof. Let \(D=\{2\}\) and \(m<n\). Suppose that \(\varphi\) is a \(\{2\}\)-irregular labeling of \(S_{m,n}\). By Theorem 2.7, \(\varphi(y_i)\ne\varphi(y_j)\) for \(i\ne j\), so \(\mathrm{s}_{\{2\}}(S_{m,n})\geqslant n\).
Assume that \(\mathrm{s}_{\{2\}}(S_{m,n})=n\). Then \(\{\varphi(y_j):j=1,2,\dots,n\}=\{1,2,\dots,n\}\), which leads to \(wt(x)=\tfrac{n(n+1)}{2}\) and \(\{wt(y_j):j=1,2,\dots,n\}=\{\tfrac{n(n+1)}{2}-n+\varphi(x),\tfrac{n(n+1)}{2}-n+1+\varphi(x),\dots,\tfrac{n(n+1)}{2}-1+\varphi(x)\}\). As \(1\leqslant\varphi(x)\leqslant n\), the vertex weights are not distinct. Therefore, \(\mathrm{s}_{\{2\}}(S_{m,n})\geqslant n+1\).
Let \(\varphi\) be a vertex labeling of \(S_{m,n}\) defined such that \[\begin{aligned} \varphi(x)&=n+1,\\ \varphi(y)&=n,\\ \varphi(x_i)&=i\quad\text{for }i=1,2,\dots,m,\\ \varphi(y_j)&=j\quad\text{for }j=1,2,\dots,n. \end{aligned}\]
Then we obtain the vertex weights as follows. \[\begin{aligned} wt(x)&=\tfrac{n(n+1)}{2},\\ wt(y)&=\tfrac{m(m+1)}{2},\\ wt(x_i)&=\tfrac{m(m+1)}{2}+n-i\quad\text{for }i=1,2,\dots,m,\\ wt(y_j)&=\tfrac{n(n+1)}{2}+n+1-j\quad\text{for }j=1,2,\dots,n. \end{aligned}\]
It is not difficult to verify that the vertex weights are distinct and the labels used in the labeling \(\varphi\) are not greater than \(n+1\), which means that \(\varphi\) is a \(\{2\}\)-irregular \((n+1)\)-labeling of \(S_{m,n}\) for \(m<n\). Hence \(\mathrm{s}_{\{2\}}(S_{m,n})=n+1\). Furthermore, combining this with Theorem 2.3 we also have \(\mathrm{s}_{\{0,1,3\}}(S_{m,n})=n+1\) for \(m<n\).
Next, we have \(\mathrm{s}_{\{0,1\}}(S_{n,n})=\mathrm{s}_{\{2,3\}}(S_{n,n})=n+1\) by Theorems 2.3 and 3.10. ◻
Lemma 3.14. Let \(S_{n,n}\) be a double star for \(n\geqslant 2\). If \(D\in\{\{0,3\},\{1,2\}\}\) then \(\mathrm{s}_D(S_{n,n})=n+2\).
Proof. Let \(D=\{0,3\}\). Define a vertex labeling \(\varphi:V(S_{n,n})\rightarrow\{1,2,\dots,n+2\}\) of \(S_{n,n}\) in the following way: \[\begin{aligned} \varphi(x)&=1,\\ \varphi(y)&=2,\\ \varphi(x_i)&=i\quad\text{for }i=1,2,\dots,n,\\ \varphi(y_i)&=i+2\quad\text{for }i=1,2,\dots,n. \end{aligned}\]
Obviously, the largest label that appears on the vertices is \(n+2\). Moreover, we have the following vertex weights. \[\begin{aligned} wt(x)&=1,\\ wt(y)&=2,\\ wt(x_i)&=\tfrac{n(n+5)}{2}+i\quad\text{for }i=1,2,\dots,n,\\ wt(y_i)&=\tfrac{n(n+1)}{2}+i+2\quad\text{for }i=1,2,\dots,n. \end{aligned}\]
It is easy to see that the vertex weights are distinct. Therefore \(\mathrm{s}_{\{0,3\}}(S_{n,n})\leqslant n+2\).
Next, we shall show that \(\mathrm{s}_{\{0,3\}}(S_{n,n})\geqslant n+2\). For a contradiction, assume that there is a \(\{0,3\}\)-irregular \((n+1)\)-labeling \(\varphi\) of \(S_{n,n}\) for \(n\geqslant 2\). Then by Theorem 2.8, the following properties hold:
\(\varphi(x_i)\ne\varphi(x_j)\) for \(i\ne j\), and
\(\varphi(y_i)\ne\varphi(y_j)\) for \(i\ne j\).
We may assume, without loss of generality, that \(\{\varphi(x_i):i=1,2,\dots,n\}=\{1,2,\dots,n\}\) and \(\{\varphi(y_i):i=1,2,\dots,n\}=\{1,2,\dots,n+1\}-\{r\}\), where \(1\leqslant r\leqslant n\). Then \[\begin{aligned} \{wt(x_i):i=1,2,\dots,n\}=&\left\{\tfrac{n(n+1)}{2}+n+2-r,\tfrac{n(n+1)}{2}+n+3-r,\dots, \tfrac{n(n+1)}{2}\right.\\ &+2n+1-r\bigg\}, \end{aligned}\] and \[\begin{aligned} \{wt(y_i):i=1,2,\dots,n\}=&\left\{\tfrac{n(n+1)}{2}+1,\tfrac{n(n+1)}{2}+2,\dots, \tfrac{n(n+1)}{2}+n+1\right\}\\ &-\left\{\tfrac{n(n+1)}{2}+r\right\}. \end{aligned}\]
Since these sets are not disjoint, the vertex weights are not distinct, a contradiction. Thus\(\mathrm{s}_{\{0,3\}}(S_{n,n})\geqslant n+2\).
As \(n+2\leqslant\mathrm{s}_{\{0,3\}}(S_{n,n})\) and \(\mathrm{s}_{\{0,3\}}(S_{n,n})\leqslant n+2\) we conclude that \(\mathrm{s}_{\{0,3\}}(S_{n,n})=n+2\). Furthermore, combining this with Theorem 2.3 we get \(\mathrm{s}_{\{1,2\}}(S_{n,n})=n+2\). ◻
Lemma 3.15. Let \(S_{n,n}\) be a double star for \(n\geqslant 1\). If \(D\in\{\{2\},\{0,1,3\}\}\) then \(\mathrm{s}_D(S_{n,n})=n+3\).
Proof. Let \(D=\{2\}\). Define a vertex labeling \(\varphi:V(S_{n,n})\rightarrow\{1,2,\dots,n+3\}\) of \(S_{n,n}\) in the following way: \[\begin{aligned} \varphi(x)&=n+3,\\ \varphi(y)&=n+1,\\ \varphi(x_i)&=i\quad\text{for }i=1,2,\dots,n,\\ \varphi(y_i)&=i+2\quad\text{for }i=1,2,\dots,n. \end{aligned}\] Then we get the following vertex weights. \[\begin{aligned} wt(x)&=\tfrac{n(n+5)}{2},\\ wt(y)&=\tfrac{n(n+1)}{2},\\ wt(x_i)&=\tfrac{(n+1)(n+2)}{2}-i\quad\text{for }i=1,2,\dots,n,\\ wt(y_i)&=\tfrac{n(n+7)}{2}+1-i\quad\text{for }i=1,2,\dots,n. \end{aligned}\]
It is not hard to show that the vertex weights are distinct and the labels used in the labeling \(\varphi\) are at most \(n+3\). This means that \(\varphi\) is a \(\{2\}\)-irregular \((n+3)\)-labeling of \(S_{n,n}\) for \(n\geqslant 1\). Therefore \(\mathrm{s}_{\{2\}}(S_{n,n})\leqslant n+3\).
Next, we shall show that \(\mathrm{s}_{\{2\}}(S_{n,n})\geqslant n+3\). For a contradiction, assume that there exists a \(\{2\}\)-irregular \((n+2)\)-labeling \(\varphi\) of \(S_{n,n}\) for \(n\geqslant 1\). Using Theorem 2.7, the following properties must be hold:
\(\varphi(y)\ne\varphi(x_i)\ne\varphi(x_j)\) for \(i\ne j\), and
\(\varphi(x)\ne\varphi(y_i)\ne\varphi(y_j)\) for \(i\ne j\).
Without loss of generality we may assume that \(\{\varphi(y),\varphi(x_i):i=1,2,\dots,n\}=\{1,2,\dots,n+1\}\) and \(\{\varphi(x),\varphi(y_i):i=1,2,\dots,n\}=\{1,2,\dots,n+2\}-\{r\}\), where \(1\leqslant r\leqslant n+1\). Then \[\begin{aligned} \{wt(y),wt(x_i):i=1,2,\dots,n\}=&\left\{\tfrac{(n+1)(n+2)}{2}-n-1,\tfrac{(n+1)(n+2)}{2}-n,\dots,\right.\\ &\tfrac{(n+1)(n+2)}{2}-1\bigg\} \end{aligned}\] and \[\begin{aligned} \{wt(x),wt(y_i):i=1,2,\dots,n\}=&\left\{\tfrac{(n+1)(n+2)}{2}-r,\tfrac{(n+1)(n+2)}{2}-r+1,\dots,\right.\\ & \tfrac{(n+1)(n+2)}{2}-r+n+1\bigg\}\left\{\tfrac{(n+1)(n+2)}{2}+n\right.\\&+2-2r\bigg\}, \end{aligned}\] which implies that the vertex weights are not distinct, a contradiction. Therefore \(\mathrm{s}_{\{2\}}(S_{n,n})\geqslant n+3\).
Since \(n+3\leqslant\mathrm{s}_{\{2\}}(S_{n,n})\leqslant n+3\), we get \(\mathrm{s}_{\{2\}}(S_{n,n})=n+3\) for \(n\geqslant 1\). Moreover, combining this with Theorem 2.3 we also obtain \(\mathrm{s}_{\{0,1,3\}}(S_{n,n})=n+3\) for \(n\geqslant 1\). ◻
In the next theorem, we present \(D\)-irregularity strength for the double stars.
Theorem 3.16. Let \(S_{m,n}\) be a double star for \(1\leqslant m\leqslant n\). Then
If \(D\in\{\{1\},\{0,2,3\}\}\) then \(\mathrm{s}_D(S_{1,1})=2\).
If \(D\in\{\{0,1\},\{0,3\},\{1,2\},\{2,3\}\}\) and \(m<n\) then \(\mathrm{s}_D(S_{m,n})=n\).
If one of the following conditions is satisfied:
\(D\in\{\{2\},\{0,1,3\}\}\) and \(m<n\), or
\(D\in\{\{0,1\},\{2,3\}\}\) and \(m=n\),
then \(\mathrm{s}_D(S_{m,n})=n+1\).
If \(D\in\{\{0,3\},\{1,2\}\}\) and \(m=n\geqslant 2\) then \(\mathrm{s}_D(S_{m,n})=n+2\).
If \(D\in\{\{2\},\{0,1,3\}\}\) and \(m=n\) then \(\mathrm{s}_D(S_{m,n})=n+3\).
If \(D\in\{\{0\},\{1,2,3\}\}\) then \(\mathrm{s}_D(S_{m,n})=m+n+2\).
If one of the following conditions is satisfied:
\(D\in\{\{3\},\{0,2\},\{1,3\},\{0,1,2\},\{0,1,2,3\}\}\),
\(D\in\{\{1\},\{0,2,3\}\}\) and \((m,n)\ne(1,1)\), or
\(D\in\{\{0,3\},\{1,2\}\}\) and \(m=n=1\),
then \(\mathrm{s}_D(S_{m,n})=\infty\).
Proof. (1)-(5) follow from Lemmas 3.11, 3.12, 3.13, 3.14 and 3.15, respectively. Similarly, (6)-(7) are derived by applying Proposition 2.5, and Theorems 2.1 and 2.3. ◻
It is worth noting that, from Theorems 3.4 and 3.16, along with Corollary 3.9, we have fully characterized the \(D\)-irregularity strength for all non-trivial trees with diameter at most three, for all possible sets \(D\).
This section explores the \(\{d\}\)-irregularity strength of certain graphs with maximum degree two, focusing particularly on the disjoint union of paths and \(2\)-regular graphs, for a positive integer \(d\).
We begin by examining the \(\{d\}\)-irregularity strength of the disjoint union of paths \(mP_n\) for \(m\geqslant 1\) and \(n\geqslant 2\). For \(d=1\), the following theorem, established in [18,20], provides the result.
Theorem 4.1 [18,20]. Let \(mP_n\) be an \(m\) disjoint union of a path on \(n\) vertices for \(m\geqslant 1\) and \(n\geqslant 2\). Then \[\mathrm{s}_{\{1\}}(mP_n)= \begin{cases} 2m&\text{if }n=2,\\ \infty&\text{if }n=3,\\ \left\lceil\frac{mn}{2}\right\rceil&\text{if }n\geqslant 4. \end{cases}\]
In the next theorem, we determine \(\{d\}\)-irregularity strength of \(mP_n\) for certain \(d\geqslant 2\).
Theorem 4.2. Let \(mP_n\) be an \(m\) disjoint union of a path on \(n\) vertices for \(m\geqslant 1\) and \(n\geqslant 2\), and let \(2\leqslant d\leqslant n-1\). Then
\(\mathrm{s}_{\{\frac{n}{2}\}}(mP_n)=mn\).
For \(d\in\{\frac{n}{k}:4\leqslant k\leqslant\frac{n}{2}\}\), \(\mathrm{s}_{\{d\}}(mP_n)=\lceil\frac{mn}{2}\rceil\).
\(\mathrm{s}_{\{d\}}(mP_n)=\infty\) if and only if \[d= \begin{cases} \frac{n}{3}&\text{if }n\equiv 0\text{ }(\text{mod }d),\\ \frac{n-t}{3}\text{ or }\frac{n-t}{2}&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d,\\ n-t&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d,\text{ and }m(n-2t)\geqslant 2. \end{cases}\]
Proof. (1) Evidently, \((mP_n)_{\{\frac{n}{2}\}}\cong\frac{mn}{2}K_2\). Then by Theorem 2.9, we have \(\mathrm{s}_{\{\frac{n}{2}\}}(mP_n)=\mathrm{s}_{\{1\}}(\frac{mn}{2}K_2)=mn\).
(2) If \(d\in\{\frac{n}{k}:4\leqslant k\leqslant\frac{n}{2}\}\) then \((mP_n)_{\{d\}}\cong mdP_{\frac{n}{d}}\not\cong\frac{mn}{2}P_2\not\cong\frac{mn}{3}P_3\). By Theorems 2.9 and 4.1, \[\mathrm{s}_{\{d\}}(mP_n)=\mathrm{s}_{\{1\}}(mdP_{\frac{n}{d}})=\left\lceil\frac{mn}{2}\right\rceil.\]
(3) From Theorem 2.9 we know that \(\mathrm{s}_{\{d\}}(mP_n)=\infty\) if and only if \(\mathrm{s}_{\{1\}}((mP_n)_{\{d\}})=\infty\). Furthermore, by Theorem 2.1 we have that \(\mathrm{s}_{\{1\}}((mP_n)_{\{d\}})=\infty\) if and only if \((mP_n)_{\{d\}}\) contains at least one component isomorphic to \(P_3\) or at least two components isomorphic to \(P_1\). Thus, \(\mathrm{s}_{\{d\}}(mP_n)=\infty\) if and only if \((mP_n)_{\{d\}}\) has at least one component isomorphic to \(P_3\) or at least two components isomorphic to \(P_1\).
We have that \[(mP_n)_{\{d\}}= \begin{cases} mdP_{\frac{n}{d}}&\text{if }n\equiv 0\text{ }(\text{mod }d),\\ m(d-t)P_{\frac{n-t}{d}}\cup mtP_{\frac{n-t+d}{d}}&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d. \end{cases}\]
Clearly, \((mP_n)_{\{d\}}\) contains at least one component isomorphic to \(P_3\) if and only if \[d= \begin{cases} \frac{n}{3}&\text{if }n\equiv 0\text{ }(\text{mod }d),\\ \frac{n-t}{3}\text{ or }\frac{n-t}{2}&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d, \end{cases}\] and \((mP_n)_{\{d\}}\) has at least two components isomorphic to \(P_1\) if and only if \(n\equiv t\text{ }(\text{mod }d)\), \(0<t<d\), \(d=n-t\) and \(m(n-2t)\geqslant 2\). Therefore, combining both conditions, we conclude that \(\mathrm{s}_{\{d\}}(mP_n)=\infty\) if and only if \[d= \begin{cases} \frac{n}{3}&\text{if }n\equiv 0\text{ }(\text{mod }d),\\ \frac{n-t}{3}\text{ or }\frac{n-t}{2}&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d,\\ n-t&\text{if }n\equiv t\text{ }(\text{mod }d),\text{ }0<t<d,\text{ and }m(n-2t)\geqslant 2. \end{cases}\] ◻
Next, we address the \(\{d\}\)-irregularity strength for \(2\)-regular graphs, i.e., the disjoint union of cycles. To achieve this, we first employ the irregularity strength and edge irregularity strength of \(2\)-regular graphs to obtain \(\{1\}\)-irregularity strength of \(2\)-regular graphs. Subsequently, we use Theorem 2.9 to derive the \(\{d\}\)-irregularity strength of \(2\)-regular graphs. Recall that the edge irregularity strength of a graph \(G\), denoted by \(\mathrm{es}(G)\), is the minimum \(k\) such that an assignment of integers \(1,2,\dots,k\) to the vertices of \(G\) implies that distinct edges have distinct weights, where the edge weight is the sum of labels of its two end vertices [1].
We begin by stating the theorem of Faudree et al. [10], which determines the irregularity strength of \(2\)-regular graphs.
Theorem 4.4. ([10]). Let \(G\) be a \(2\)-regular graph on \(n\) vertices. Then \[\lfloor\tfrac{n}{2}\rfloor\leqslant\mathrm{s}(G)\leqslant\lfloor\tfrac{n}{2}\rfloor+2.\] Moreover,
If \(G\) is the disjoint union of triangles \(\frac{n}{3}C_3\) then \[\mathrm{s}(\tfrac{n}{3}C_3)= \begin{cases} \lceil\frac{n}{2}\rceil+1&\text{if }n\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+2&\text{otherwise}. \end{cases}\]
If \(G\) has no triangle then \[\mathrm{s}(G)= \begin{cases} \lceil\frac{n}{2}\rceil&\text{if }n\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+1&\text{otherwise}. \end{cases}\]
In the next theorem, we prove that the irregularity strength and the edge irregularity strength of \(2\)-regular graphs are equivalent.
Theorem 4.5. Let \(G\) be a \(2\)-regular graph on \(n\) vertices. Then \(\mathrm{es}(G)=\mathrm{s}(G)\). Consequently, \[\lfloor\tfrac{n}{2}\rfloor\leqslant\mathrm{es}(G)\leqslant\lfloor\tfrac{n}{2}\rfloor+2.\] Moreover,
If \(G\) is the disjoint union of triangles \(\frac{n}{3}C_3\) then \[\mathrm{es}(\tfrac{n}{3}C_3)= \begin{cases} \lceil\frac{n}{2}\rceil+1&\text{if }n\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+2&\text{otherwise}. \end{cases}\]
If \(G\) has no triangle then \[\mathrm{es}(G)= \begin{cases} \lceil\frac{n}{2}\rceil&\text{if }n\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+1&\text{otherwise}. \end{cases}\]
Proof. Let \(G\) be a \(2\)-regular graph on \(n\) vertices. In any edge irregular labeling of \(G\), if we shift the label of each vertex to the edge incident to it in the clockwise direction, we obtain an irregular labeling of \(G\). This demonstrates that \(\mathrm{es}(G)\geqslant\mathrm{s}(G)\). Conversely, in any irregular labeling of \(G\), shifting the label of each edge to the vertex incident to it in the clockwise direction results in an edge irregular labeling of \(G\), implying that \(\mathrm{es}(G)\leqslant\mathrm{s}(G)\). Consequently, \(\mathrm{es}(G)=\mathrm{s}(G)\). The rest of the theorem follows immediately from Theorem 4.4. ◻
Let \(G\cong mC_3\cup(G-mC_3)\) be a \(2\)-regular graph on \(n\) vertices containing \(m\) triangles and no square. Evidently, \(mC_3\cup (G-mC_3)_{\{2\}}\) is a \(2\)-regular graph with \(n\) vertices. Moreover, it is not hard to know that every \(\{1\}\)-irregular labeling of \(G\) induces an edge irregular labeling of \(mC_3\cup (G-mC_3)_{\{2\}}\), and every edge irregular labeling of \(mC_3\cup (G-mC_3)_{\{2\}}\) induces a \(\{1\}\)-irregular labeling of \(G\), meaning that \(\{1\}\)-irregularity strength of \(G\) and edge irregularity strength of \(mC_3\cup (G-mC_3)_{\{2\}}\) are equivalent.
Further, if \(G\cong mC_3\cup\frac{n-3m}{6}C_6\) then \(mC_3\cup(\frac{n-3m}{6}C_6)_{\{2\}}\) is the disjoint union of triangles \(\frac{n}{3}C_3\), and if \(m=0\) and \(G\) has no hexagon then \(G_{\{2\}}\) is a \(2\)-regular graph without any triangle.
With the above facts in hand along with Theorem 4.5 we obtain the following.
Theorem 4.6. Let \(G\cong mC_3\cup(G-mC_3)\) be a \(2\)-regular graph on \(n\) vertices containing \(m\) triangles and no square for \(n\geqslant 3\) and \(0\leqslant m\leqslant\frac{n}{3}\). Then \(\mathrm{s}_{\{1\}}(G)=\mathrm{es}(mC_3\cup(G-mC_3)_{\{2\}})\). Consequently, \[\lfloor\tfrac{n}{2}\rfloor\leqslant\mathrm{s}_{\{1\}}(G)\leqslant\lfloor\tfrac{n}{2}\rfloor+2.\] Moreover,
If \(G=mC_3\cup\frac{n-3m}{6}C_6\) then \[\mathrm{s}_{\{1\}}(G)= \begin{cases} \lceil\frac{n}{2}\rceil+1&\text{if }n\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+2&\text{otherwise}. \end{cases}\]
If \(m=0\) and \(G\) has no hexagon then \[\mathrm{s}_{\{1\}}(G)= \begin{cases} \lceil\frac{n}{2}\rceil&\text{if }n\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+1&\text{otherwise}. \end{cases}\]
The next theorem provides \(\{d\}\)-irregularity strength of the isomorphic copies of cycles \(mC_n\) for \(1\leqslant d\leqslant\lfloor\frac{n}{2}\rfloor\).
Theorem 4.7. Let \(mC_n\) be an \(m\) disjoint union of a cycle on \(n\) vertices for \(m\geqslant 1\) and \(n\geqslant 3\). Then
\(\mathrm{s}_{\{\frac{n}{4}\}}(mC_n)=\infty\).
\(\mathrm{s}_{\{\frac{n}{2}\}}(mC_n)=mn\).
For \(d\in\{\frac{n}{6},\frac{n}{3}\}\), \[\mathrm{s}_{\{d\}}(mC_n)= \begin{cases} \lceil\frac{mn}{2}\rceil+1&\text{if }mn\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{mn}{2}\rceil+2&\text{otherwise}. \end{cases}\]
For \(d\in(\{1,2,\dots,\lfloor\frac{n}{2}\rfloor\}-\{\frac{n}{6},\frac{n}{4},\frac{n}{3},\frac{n}{2}\})\), \[\mathrm{s}_{\{d\}}(mC_n)= \begin{cases} \lceil\frac{mn}{2}\rceil&\text{if }mn\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{mn}{2}\rceil+1&\text{otherwise}. \end{cases}\]
Proof. By simple observation, \((mC_n)_{\{\frac{n}{4}\}}=\frac{mn}{4}C_4\) and \((mC_n)_{\{\frac{n}{2}\}}=\frac{mn}{2}K_2\). Then by Theorem 2.9, we find that \(\mathrm{s}_{\{\frac{n}{4}\}}(mC_n)=\mathrm{s}_{\{1\}}(\frac{mn}{4}C_4)=\infty\) and \(\mathrm{s}_{\{\frac{n}{2}\}}(mC_n)=\mathrm{s}_{\{1\}}(\frac{mn}{2}K_2)=mn\). This proves (1) and (2).
Next, let \(d\in\{\frac{n}{6},\frac{n}{3}\}\). If \(d=\frac{n}{6}\) then \((mC_n)_{\{\frac{n}{6}\}}=\frac{mn}{6}C_6\). By Theorems 2.9 and 4.6, we obtain \[\mathrm{s}_{\{\frac{n}{6}\}}(mC_n)=\mathrm{s}_{\{1\}}(\tfrac{mn}{6}C_6)= \begin{cases} \lceil\frac{mn}{2}\rceil+1&\text{if }mn\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{mn}{2}\rceil+2&\text{otherwise}. \end{cases}\] If \(d=\frac{n}{3}\) then \((mC_n)_{\{\frac{n}{3}\}}=\frac{mn}{3}C_3\). Again, by Theorems 2.9 and 4.6, we have \[\mathrm{s}_{\{\frac{n}{3}\}}(mC_n)=\mathrm{s}_{\{1\}}(\tfrac{mn}{3}C_3)= \begin{cases} \lceil\frac{mn}{2}\rceil+1&\text{if }mn\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{mn}{2}\rceil+2&\text{otherwise}. \end{cases}\] This proves 3.
Now, for \(d\in(\{1,2,\dots,\lfloor\frac{n}{2}\rfloor\}-\{\frac{n}{6},\frac{n}{4},\frac{n}{3},\frac{n}{2}\})\), we observe that \((mC_n)_{\{d\}}\) is a \(2\)-regular graph without any cycle \(C_t\) for \(t=3,4,6\). By Theorems 2.9 and 4.6, we conclude that \[\mathrm{s}_{\{d\}}(mC_n)=\mathrm{s}_{\{1\}}((mC_n)_{\{d\}})= \begin{cases} \lceil\frac{mn}{2}\rceil&\text{if }mn\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{mn}{2}\rceil+1&\text{otherwise}. \end{cases}\] Hence (4) is proved. ◻
Under certain conditions, Theorem 4.7 can be extended to \(2\)-regular graphs that contain non-isomorphic cycle components.
Theorem 4.8. Let \(G=\bigcup_{i=1}^m C_{n_i}\) be a \(2\)-regular graph on \(n=n_1+n_2+\dots+n_m\) vertices with \(m\geqslant 2\) components such that \(3\leqslant n_1\leqslant n_2\leqslant\dots\leqslant n_m\), and \(G\not\cong mC_p\) for some \(p\geqslant 3\). Then
For \(d\in(\{\frac{n_i}{4}\leqslant\lfloor\frac{n_1}{2}\rfloor:i=1,2,\dots,m\}\cup\{\lfloor\frac{n_{1}}{2}\rfloor+1,\lfloor\frac{n_{1}}{2}\rfloor+2,\dots,\lfloor\frac{n_m}{2}\rfloor\})\), \(\mathrm{s}_{\{d\}}(G)=\infty\).
For \(d\in(\{\frac{n_i}{6},\frac{n_i}{3}\leqslant\lfloor\frac{n_1}{2}\rfloor:i=1,2,\dots,m\}-\{\frac{n_j}{4},\frac{n_j}{2}:j=1,2,\dots,m\})\), \[\lfloor\tfrac{n}{2}\rfloor\leqslant\mathrm{s}_{\{d\}}(G)\leqslant\lfloor\tfrac{n}{2}\rfloor+2.\] In particular, if \(d\in\{\frac{n_i}{6},\frac{n_i}{3}\}\) for some \(i\), and \(\frac{n_j}{\gcd{(n_j,d)}}\in\{3,6\}\) for every \(j=1,2,\dots,m\), \(j\neq i\), then \[\mathrm{s}_{\{d\}}(G)= \begin{cases} \lceil\frac{n}{2}\rceil+1&\text{if }n\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+2&\text{otherwise}. \end{cases}\]
For \(d\in(\{1,2,\dots,\lfloor\frac{n_1}{2}\rfloor\}-\{\frac{n_j}{6},\frac{n_j}{4},\frac{n_j}{3},\frac{n_j}{2}:j=1,2,\dots,m\})\), \[\mathrm{s}_{\{d\}}(G)= \begin{cases} \lceil\frac{n}{2}\rceil&\text{if }n\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+1&\text{otherwise}. \end{cases}\]
Proof. (1) If \(d\in\{\frac{n_i}{4}\leqslant\lfloor\frac{n_1}{2}\rfloor:i=1,2,\dots,m\}\) then \(G_{\{d\}}\) contains a square, and so \(\mathrm{s}_{\{d\}}(G)=\mathrm{s}_{\{1\}}(G_{\{d\}})=\infty\). If \(d\in\{\lfloor\frac{n_1}{2}\rfloor+1,\lfloor\frac{n_1}{2}\rfloor+2,\dots,\lfloor\frac{n_m}{2}\rfloor\}\) then \(N_{\{d\}}(x)=N_{\{d\}}(y)=\emptyset\) for any two distinct vertices \(x\) and \(y\) in the component \(C_{n_1}\), thus \(\mathrm{s}_{\{d\}}(G)=\infty\).
(2) If \(d\in(\{\frac{n_i}{6},\frac{n_i}{3}\leqslant\lfloor\frac{n_1}{2}\rfloor:i=1,2,\dots,m\}-\{\frac{n_j}{4},\frac{n_j}{2}:j=1,2,\dots,m\})\) then \(G_{\{d\}}\cong tC_3\cup(G_{\{d\}}-tC_3)\) is a \(2\)-regular graph of order \(n\) containing \(t\) triangles and no square for some \(t\geqslant 0\). Therefore, by Theorems 2.9 and 4.6, \[\lfloor\tfrac{n}{2}\rfloor\leqslant\mathrm{s}_{\{d\}}(G)=\mathrm{s}_{\{1\}}(G_{\{d\}})\leqslant\lfloor\tfrac{n}{2}\rfloor+2.\] For some \(i\), let \(d\in\{\frac{n_i}{6},\frac{n_i}{3}\}\), and for every \(j=1,2,\dots,m\), \(j\ne i\), let \(\frac{n_j}{\mathrm{gcd}(n_j,d)}\in\{3,6\}\). Then \(G_{\{d\}}\cong m_1C_3\cup m_2C_6\), where \(3m_1+6m_2=n\). Thus, by Theorems 2.9 and 4.6, \[\mathrm{s}_{\{d\}}(G)=\mathrm{s}_{\{1\}}(G_{\{d\}})= \begin{cases} \lceil\frac{n}{2}\rceil+1&\text{if }n\equiv 3\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+2&\text{otherwise}. \end{cases}\]
(3) If \(d\in(\{1,2,\dots,\lfloor\frac{n_1}{2}\rfloor\}-\{\frac{n_j}{6},\frac{n_j}{4},\frac{n_j}{3},\frac{n_j}{2}:j=1,2,\dots,m\})\) then \(G_{\{d\}}\) is a \(2\)-regular graphs with \(n\) vertices containing no cycle \(C_t\), \(t=3,4,6\). By Theorems 2.9 and 4.6, \[\mathrm{s}_{\{d\}}(G)=\mathrm{s}_{\{1\}}(G_{\{d\}})= \begin{cases} \lceil\frac{n}{2}\rceil&\text{if }n\equiv 1\text{ }(\mathrm{mod}\text{ }4),\\ \lceil\frac{n}{2}\rceil+1&\text{otherwise}. \end{cases}\] ◻
In this work, we introduced a \(D\)-irregular labeling as a generalization of non-inclusive and inclusive \(d\)-distance irregular labeling of graphs. We derived fundamental properties on \(D\)-irregularity strength for arbitrary graphs, and presented exact values on this parameter for specific families of graphs with small diameter or small maximum degree.
The authors of [16] posed a conjecture below.
Conjecture 5.1 ([16]) A graph \(G\) is \(D\)-antimagic if and only if \(N_D(x)\ne N_D(y)\) for every two distinct vertices \(x,y\in V(G)\).
Note that if Conjecture 5.1 holds, then for a graph \(G\) with finite \(D\)-irregularity strength, the inequality \(\mathrm{s}_D(G)\leqslant |V(G)|\) holds as well. Motivated by this observation and the results presented in Proposition 2.5, we believe that the following conjecture is true.
\(G\) is connected and \(D\in\{\{0\},\{1,2,\dots,\mathrm{diam}(G)\}\}\),
\(G\cong mK_2\), \(m\geqslant 2\), and \(D=\{\{0\},\{1\}\}\), or
\(G\) is disconnected, \(G\not\cong mK_2\), \(m\geqslant 2\), and \(D=\{0\}\).
This work has been supported by Direktorat Riset, Teknologi, dan Pengabdian kepada Masyarakat, Direktorat Jenderal Pendidikan Tinggi, Riset, dan Teknologi, Kementerian Pendidikan, Kebudayaan, Riset, dan Teknologi Republik Indonesia under the grant “Penelitian Fundamental Reguler 2024” and by Institut Teknologi Bandung under the grant “Program Riset International 2023/2024”. The first author gratefully acknowledges the support provided by the Excellent Scholarship Program of the Indonesian Ministry of Education, Culture, Research, and Technology.