Some new results on sum index and difference index

1.   Introduction

Let $G = (V(G), E(G))$ be a simple graph, where $V(G)$ is the set of vertices of $G$ and $E(G)$ is the set of edges of $G$. Two edges $e_{1}$ and $e_{2}$ of $G$ are adjacent, if they have exactly one common end vertex (otherwise, $e_{1}$ and $e_{2}$ of $G$ are non-adjacent). If $e = \left\lbrace u, v\right\rbrace$ is an edge of $G$, then $u$ and $v$ are adjacent while $u$ and $e$ are incident. If all the vertices of $G$ have the same degree $d$, then $G$ is $d$-regular and its degree sequence is $\pi = (d, d, \cdots, d)$. Let $G^{\prime} = (V(G^{\prime}), E(G^{\prime}))$, we call $G^{\prime}$ is a subgraph of $G$ if $V(G^{\prime})\subseteq V(G)$ and $E(G^{\prime})\subseteq E(G)$. If $G^{\prime}$ contains all the edges $uv\in E(G)$ with $u, \; v\in V(G^{\prime})$, then $G^{\prime}$ is an induced subgraph of $G$.

The complement of $G$ denoted by $\overline{G}$, is the simple graph whose vertex set is $V(G)$ and whose edges are the pairs of non-adjacent vertices of $G$. A matching of a graph $G$ is a set of pairwise non-adjacent edges in $E(G)$. A $m$-matching is a matching consisting of $m$ edges denoted by $mK_2$. As usual, we use $P_n$ and $C_n$ to denote the path and cycle of order $n$, respectively.

Let $f:V\left (G \right)\to \mathbb{Z}$ be an injective vertex labeling of $G$. There are two edge labelings of $G$ induced by $f$, which are defined as $f^{+} :E\left (G \right)\to \mathbb{Z}$ and $f^{-} :E\left (G \right)\to \mathbb{Z}$. For each edge $uv\in E(G)$, two edge labelings $f^{+}(uv)$ and $f^{-}(uv)$ are defined by

The sum index $s(G)$ and difference index $d(G)$ of $G$ are defined by the minimum ranges of $f^{+}$ and $f^{-}$ of $G$, respectively. They were introduced by Harrington et al. in ^[1]. To avoid much ambiguity, we denote $f^{-}$ by $g^{-}$. The injective vertex labeling corresponding to $g^{-}$ is denoted by $g$ throughout the article.

Definition 1.1. ^[1] The sum index of $G$, denoted by $s(G)$, is the minimum positive integer $k$ such that there exists a vertex labeling $f$ of $G$ satisfying $\left|f^{+}\right| = k$, where $\left|f^{+}\right|$ is the range of $f$. A vertex labeling $f$ such that $\left|f^{+}\right| = s(G)$ is referred to as a sum index labeling of $G$.

Definition 1.2. ^[1] Let $g: V(G) \rightarrow \mathbb{Z}$ be a vertex labeling of $G$, and let $g^{-}: E(G) \rightarrow \mathbb{Z}$ be the induced edge labeling defined by $g^{-}(u v) = |g(u)-g(v)|$ for each edge $u v \in E(G)$. The difference index of $G$, denoted by $d(G)$, is the minimum positive integer $k$ such that there exists a vertex labeling $g$ of $G$ satisfying $\left|g^{-}\right| = k$, where $\left|g^{-}\right|$ is the range of $g$. A vertex labeling $g$ such that $\left|g^{-}\right| = d(G)$ is referred to as a difference index labeling of $G$.

Degree-based indices are served as meaningful models for a broad range of applications. For example, the Randić index ^[2] is denoted by

where $d_G(u)$ is the degree of the vertex $u\in V(G)$. The Randić index has great applications in modeling the properties of certain molecular structures. As another important degree-based topological index, the Sombor index ^[3] is used to model the higher-order interactions represented by clique structures and defined by

The $\text{atom-bond connectivity}\; (ABC) \; {\rm{index}}$ of $G$ has proven to be a valuable predictive index in the study of the heat of function in alkanes ^[4,5] and defined by

In graph theory, regular graphs are one of the most important classes of graphs. Let $G_{0}$ be $d$-regular with order $n$. Then the above three indices are $R(G_{0}) = \frac{n}{2}, \; SO(G_{0}) = \frac{\sqrt{2}}{2}d^{2}n\; \text{and}\; ABC(G_{0}) = \frac{n\sqrt{2d-2}}{2}.$ Moreover, the first Zagreb index ^[6], the variable sum exdeg index ^[7], the Harmonic index ^[8] and so on are all widely used in graphs including regular graphs.

Graph indices derived from graph labelings are also of great value in coding theory, radar, circuit design, data base management and among others. The notations of the (integral) sum labelings of graphs were introduced by F. Harary in ^[9]. Since that time the problems of finding the (integral) sum numbers and proving the (integral) sum graphs have been studied and discussed by scholars referring to ^[10,11]. A graph $G$ is called an (integral) sum graph if there is a bijection $f$ from $V(G)$ to $S\subset \left(\mathbb{Z}\right) \; \mathbb{N}$ such that $xy\in E(G)$ if and only if $f(x)+f(y)\in S$. The (integral) sum number of $G$ is the minimum number of isolated vertices that must be added to $G$ such that the resulting graph is an (integral) sum graph.

Based on the above, graph labelings of graphs attracted lots of attention of researchers. For example, the vertex-magic total labelings were introduced by MacDougall, Miller, Slamin and Wallis in ^[12]. Ponraj and Parthipan posited pair sum labelings in ^[13]. Harrington and Wong used super totient numbers to label vertices of graphs and found that the restricted super totient indices of graphs were equal to their sum indices in ^[14]. In this regard, Harrington, Henninger-Voss et al. defined the sum indices and difference indices of graphs and lower bounds on these two indices were also determined in ^[1]. Further, both the sum and difference indices of several graphs were also obtained such as the complete graphs, complete bipartite graphs, caterpillars, cycles, wheels and rectangular grids in ^[1]. Besides, Haslegrave improved bounds on these two indices in ^[15].

Up to now, some useful results about the sum indices and difference indices of graphs are shown as follows.

Property 1.1. ^[14] The sum index is greater than or equal to the maximum degree of $G$,

Property 1.2. ^[1] The sum index is greater than or equal to the chromatic index of $G$,

Property 1.3. ^[1] Let $\delta(G)$ be the minimum degree of $G$, and recall that $\chi^{\prime}(G)$ is the chromatic index of $G$. Then we have

Property 1.4. ^[15] For any graph G, we have

In this paper, we continue to study the sum indices and difference indices of graphs. Firstly, we improve some bounds on the sum and difference indices in Section 2. In particular, we find relationships about these two indices between a graph $G$ and its induced subgraph $G^{\prime}$. For regular graphs, we make slight generalizations of Haslegrave's bounds on the sum and difference indices in ^[15]. Secondly, we obtain the sum and difference indices of some graphs in Section 3 such as the necklace graphs, the complements of matchings, cycles and paths. Finally, we compare the sum indices with (integral) sum numbers and analyze the sum and difference indices of regular graphs. Combined with conclusions of the paper, we also put forward some conjectures and open questions.

2.   Properties and bounds of sum indices and difference indices of graphs

In this section, we explore the properties of sum index labelings and difference index labelings of graphs. We also improve the bounds on the sum and difference indices of regular graphs and induced subgraphs of graphs. In particular, we make slight improvements to Property 1.4 such that we can directly determine lower bounds on the sum indices and difference indices of regular graphs.

Theorem 2.1. If $f$ is a sum index labeling of $G$, then $kf$ is also a sum index labeling of $G$ for any non-zero integer. The result holds for a difference index labeling $g$ as well.

Proof. If $f$ is a sum index labeling of $G$, then $\left | f^{+} \right | = s(G)$. Denote $s(G) = s$ and $f^{+} = \left\{\alpha_1, \alpha_2, \cdots, \alpha_s\right\}$, where $\alpha_1, \alpha_2, \cdots, \alpha_s$ are integers. According to the definition of $s(G)$, one has

Hence we observe that

Thus $kf$ is also a sum index labeling of $G$. □

Remark 2.1. For a graph $G$, the sum index of $G$ is unique, while the number of corresponding sum index labelings is infinite.

Theorem 2.2. Let $G^{\prime}$ be an induced subgraph of a graph $G$. Then $s(G^{\prime}) \le s(G)$ and $d(G^{\prime})\le d(G)$.

Proof. Let $V(G) = \left \{ v_{1}, v_{2}, v_{3}, \cdots, v_{n}\right \}$ and $V(G^{\prime}) = \left \{ v_{i_{1}}, v_{i_{2}}, v_{i_{3}}, \cdots, v_{i_{j}}\right \}$, where $V(G^{\prime})\subset V(G)$ for $i\in\mathbb{Z}$ and $j\le n$. For any vertex $v_{i_{k}}$ in $G^{\prime}$, we can always find a vertex $v_{l}$ in $G$ such that $v_{i_{k}} = v_{l}$ for $1\le k \le j$ and $1\le l \le n$. If $f$ is a sum index labeling and $g$ is a difference index labeling of $G$, then $\left | f^{+} \right | = s(G)$ and $\left | g^{-} \right | = d(G)$. For each vertex labeling $f^{\prime}$ and $g^{\prime}$ of $G^{\prime}$, let $f^{\prime}(v_{i_{k}}) = f(v_{l})$ and $g^{\prime}(v_{i_{k}}) = g(v_{l})$. Thus we have

□

Theorem 2.3. Let $G$ be $d$-regular with order $n$. Then $s(G)\ge 2d-1$ and $d(G)\ge d$.

Proof. Let $f :V(G)\to \mathbb{Z}$ be an injective vertex labeling of $G$. Denote $f:V(G)\to \left \{ a_{1}, a_{1}, \cdots, a_{n}\right \}$, where $a_{1}, a_{1}, \cdots, a_{n}$ are integers such that $a_{1} < a_{2} < \cdots < a_{n}$. It follows that

Note that $G$ is a $d$-regular graph. Then the sum of the two numbers above has at most $2(n-1-d)$ elements which do not belong to $f^{+}$. Thus, we obtain

Next, we will show that $d(G)\ge d$. Let $g = f$ be an injective vertex labeling of $G$. Without loss of generality, we assume that the vertex labeled $a_{1}$ is adjacent to vertices labeled $a_{2}$, $a_{3}$, $\cdots$, $a_{d+1}$. By utilizing the definition of $d(G)$, we have $d(G)\ge d$. □

Remark 2.2. Theorem 2.3 is viewed as slight generalizations of Haslegrave's bounds on the sum and difference indices of graphs in ^[15] (see Property 1.4).

3.   Sum indices and difference indices of some graphs

In this section, we discuss the sum indices and difference indices of some graphs such as the necklace graphs, the complements of matchings, cycles and paths. At the beginning, we introduce a difinition about the edge labeling of a graph that will be needed in the remaining part of the paper.

Definition 3.1. For two edge labelings $f^{+}$ and $g^{-}$ of $G$, the contributing elements of $f^{+}$ are the elements first appearing in $f^{+}$. For each edge $v_i v_j \in E(G)$, let $f^{\prime+}\left(v_i v_j\right)$ be a contributing set of $f^{+}$, which is a set of all contributing elements of $f^{+}$. Define $\left|f^{\prime+}\left(v_i v_j\right)\right|$ as contributions corresponding to $f^{\prime+}\left(v_i v_j\right)$ of $f^{+}$. If $f^{\prime+}\left(v_i v_j\right) = \emptyset$, then $\left|f^{\prime+}\left(v_i v_j\right)\right| = 0$. The definitions of $g^{\prime-}\left(v_i v_j\right)$ and $\left|g^{\prime-}\left(v_i v_j\right)\right|$ are similar to $f^{\prime+}\left(v_i v_j\right)$ and $\left|f^{\prime+}\left(v_i v_j\right)\right|$, respectively.

According to Definition 3.1, it is not difficult to find that

Remark 3.1. ^[1] For the matching $mK_{2}$ with $m\ge 1$, we have $s(mK_{2}) = 1$ and $d(mK_{2}) = 1$. The inverse problem is also true.

Remark 3.2. ^[1] For the cycle $C_{n}$ with $n\ge 3$, we have $s(C_{n}) = 3$ and $d(C_{n}) = 2$.

Theorem 3.1. For the necklace graph, or briefly by $N_{ek}$ for $k\ge 1$, we have $s(N_{ek}) = 5$ and $d(N_{ek}) = 3$.

Proof. Note that the degree sequence of $N_{ek}$ is $\pi = (3, 3, \cdots, 3)$, and hence $s(N_{ek})\ge5$ by Theorem 2.3. In what follows, we just find a vertex labeling $f$ such that $\left| f^+\right| = 5$.

Let $f:V(N_{ek})\to \mathbb{Z}$ be an injective labeling, where $V\left(N_{e k}\right) = \left\{a_1, a_2, \ldots, a_k, b_1, b_2, \ldots, b_k, c_1, c_2\right\}$. For $1\le i \le k$, we label the vertices in $V(N_{ek})$ according to the following scheme.

where $c_{1}a_{1}\in E(N_{ek})$, $c_{1}b_{1}\in E(N_{ek})$, $c_{1}c_{2}\in E(N_{ek})$, $c_{2}a_{k}\in E(N_{ek})$, $c_{2}b_{k}\in E(N_{ek})$, $a_{1}b_{1}\in E(N_{ek})$, $a_{1}a_{2}\in E(N_{ek})$ and $b_{1}b_{2}\in E(N_{ek})$. For $2\le i \le k-1$, we observe that $a_{i-1}a_{i}\in E(N_{ek})$, $a_{i}a_{i+1}\in E(N_{ek})$, $a_{i}b_{i}\in E(N_{ek})$, $b_{i-1}b_{i}\in E(N_{ek})$ and $b_{i}b_{i+1}\in E(N_{ek})$ (see Figure 1).

It is clear to see that under the vertex labeling $f$ we have

On the other hand, we will show that $d(N_{ek}) = 3$. Since we know $d(N_{ek})\ge 3$ by Theorem 2.3, it suffices to find a vertex labeling $g$ such that $\left|g^{-} \right| = 3$.

Let $g:V(N_{ek})\to \mathbb{Z}$ be an injective vertex labeling of $N_{ek}$. For $1\le i \le k$, we consider the vertex labeling $g$ defined such that

It is clear to see that

We illustrate the vertex labelings $f$ and $g$ of $N_{e4}$, respectively (see Figure 2). □

Remark 3.3. ^[1,15] The prism graph is also 3-regular, which satisfies $s(\Pi _{n}) = 5\; {and}\; d(\Pi _{n}) = 3$.

Theorem 3.2. The complement of a matching $mK_2$, or briefly by $\overline{m K_2}$, is $(n-2)$-regular for $m\ge 4$. Then

Proof. Throughout this proof, since the complement of a matching $mK_2$ is $(n-2)$-regular. The degree sequence of $\overline{m K_2}$ is $\pi = (n-2, n-2, \cdots, n-2)$. According to the properties of degree sequence, we know $\sum_{v\in V(G)} d_G(v) = 2|E|$. It implies that $n$ is even.

Firstly, we discuss the sum index of $\overline{m K_2}$. By Theorem 2.3, we have $s(\overline{m K_2})\ge 2n-5$. Then we just find a vertex labeling $f$ such that $\left| f^+\right| = 2n-5$. For $1\le i\le n$, let $f:V(\overline{m K_2})\to \mathbb{Z}$ be an injective labeling such that

where $v_{j}v_{j+1}\notin E(\overline{m K_2})$ and $v_{n+1} = v_{1}$ for $2\le j \le n$ and $j$ is even.

According to the labeling $f$ and Definition 3.1, we observe that the following three equations hold.

Except the above contributions corresponding three contributing sets, the sum of other contributions of $f^{+}$ is equal to $0$. Therefore we know

Next, we consider the difference index of $\overline{m K_2}$. Note that $d(\overline{m K_2})\ge n-2$ by Theorem 2.3. It remains to show that $d(\overline{m K_2})\le n-2$. Let $g:V(\overline{m K_2})\to \mathbb{Z}$ be an injective labeling, where $g(v_{i}) = f(v_{i})$ for $1\le i\le n$. We assume that all vertices of $\overline{m K_2}$ satisfy $v_{j}v_{j+1}\notin E(\overline{m K_2})$, when $j$ is odd and $1\le j \le n-1$.

By Definition 3.1, it holds that

The sum of other contributions of $g^{-}$ is equal to $0$, if the contributions corresponding two contributing sets above are excluded. Thus we have

We illustrate the vertex labelings $f$ and $g$ of $\overline{6K_2}$, respectively (see Figure 3). □

Next, we achieve the following theorems of the complements of a cycle $C_{n}$ and a path $P_n$ relating to sum and difference indices, respectively.

Theorem 3.3. The complement of a cycle $C_{n}$, or briefly by $\overline{C_{n}}$, is $(n-3)$-regular for $n\ge 6$. Then

Proof. To begin with, we consider the sum index of $\overline{C_{n}}$. By Theorem 2.3, we have $s(\overline{C_{n}})\ge 2n-7$. It remains to show that $s(\overline{C_{n}})\le2n-7$ by defining a vertex labeling $f$ such that $\left| f^+\right| = 2n-7$. For $1\le i \le n$, let $f:V(\overline{C_{n}})\to \mathbb{Z}$ be an injective labeling such that

In what follows, we distinguish two cases according to the parity of $n$.

${\bf{Case}} \; {\bf{1}}.$ If $n$ is even.

In this case, we assume that $v_{1}v_{2}\notin E(\overline{C_{n}})$ and $v_{n-1}v_{n}\notin E(\overline{C_{n}})$. For each $1\le m\le \frac{n-2}{2}$, all vertices of $\overline{C_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{C_{n}})$ and $v_{2m-1}v_{2m+1}\notin E(\overline{C_{n}})$. Then Definition 3.1 implies that

Except the above contributions corresponding three contributing sets, the sum of other contributions of $f^{+}$ is equal to $0$. Therefore we obtain

${\bf{Case}} \; {\bf{2}}.$ If $n$ is odd.

If $n$ is odd, we assume that $v_{1}v_{2}\notin E(\overline{C_{n}})$, $v_{1}v_{3}\notin E(\overline{C_{n}})$ and $v_{n-1}v_{n}\notin E(\overline{C_{n}})$. For each $1\le m\le \frac{n-3}{2}$, all vertices of $\overline{C_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{C_{n}})$ and $v_{2m+1}v_{2m+3}\notin E(\overline{C_{n}})$. Further, Definition 3.1 implies that

The sum of other contributions of $f^{+}$ is equal to $1$, if the contributions above are excluded. Thus based on the definition of the sum index, we obtain

We illustrate the sum index labelings $f$ of $\overline{C_7}$ and $\overline{C_8}$, respectively (see Figure 4).

On the other hand, we consider the difference index of $\overline{C_{n}}$. Note that $d(\overline{C_{n}})\ge n-3$ by Theorem 2.3. Then it remains to show that $d(\overline{C_{n}})\le n-3$. For $1\le i\le n$, let $g:V(\overline{C_{n}})\to \mathbb{Z}$ be an injective labeling such that $g(v_{i}) = f(v_{i})$. Below, we distinguish two cases according to the parity of $n$.

Case 1. If $n$ is even.

If $n$ is even, then we assume that $v_{1}v_{2}\notin E(\overline{C_{n}})$ and $v_{n-1}v_{n}\notin E(\overline{C_{n}})$. And for each $1\le m\le \frac{n-2}{2}$, all vertices of $\overline{C_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{C_{n}})$ and $v_{2m-1}v_{2m+1}\notin E(\overline{C_{n}})$.

In addition, Definition 3.1 enables us to ensure that

The sum of other contributions of $g^{-}$ is equal to $0$, if the contributions corresponding two contributing sets above are excluded. Thus, we have

Case 2. If $n$ is odd.

If $n$ is odd, then we assume that $v_{1}v_{2}\notin E(\overline{C_{n}})$, $v_{1}v_{3}\notin E(\overline{C_{n}})$, $v_{n-5}v_{n-2}\notin E(\overline{C_{n}})$, $v_{n-4}v_{n-3}\notin E(\overline{C_{n}})$, $v_{n-3}v_{n}\notin E(\overline{C_n})$, $v_{n-2}v_{n-1}\notin E(\overline{C_n})$ and $v_{n-1}v_{n}\notin E(\overline{C_{n}})$. And for each $1\le m\le \frac{n-7}{2}$, all vertices of $\overline{C_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{C_{n}})$ and $v_{2m+1}v_{2m+3}\notin E(\overline{C_{n}})$. By Definition 3.1, it holds that

Except the above contributions corresponding two contributing sets, the sum of other contributions of $g^{-}$ is equal to $0$. It is clear to see that under the vertex labeling $g$ we have

We illustrate difference index labelings $g$ of $\overline{C_7}$ and $\overline{C_8}$, respectively (see Figure 5).

□

Theorem 3.4. Let $\overline{P_{n}}$ be the complement of a path $P_{n}$ for $n\ge 6$. Then

Proof. In this proof, let $\overline{P_{n}}$ be the complement of a path $P_{n}$ for $n\ge 6$. Then its degree sequence is $\pi = (n-2, n-2, n-3, n-3, \cdots, n-3)$. Without loss of generality, we assume that $d\left(v_1\right) = d\left(v_2\right) = n-2, \; d\left(v_i\right) = n-3$ for $3 \leq i \leq n$.

Firstly, we discuss the sum index of $\overline{P_{n}}$. Property 1.4 implies that $s(\overline{P_{n}})\ge 2n-6$. Then it remains to show that $s(\overline{C_{n}})\le2n-7$ by defining a vertex labeling $f$ such that $\left| f^+\right| = 2n-6$. Let $f:V(\overline{C_{n}})\to \mathbb{Z}$ be an injective labeling of $\overline{C_{n}}$ such that

for $1\le i \le n$. Below, we distinguish two cases according to the parity of $n$.

Case 1. If $n$ is even.

If $n$ is even, then we assume that $v_{1}v_{2}\notin E(\overline{P_{n}})$ and $v_{n-1}v_{n}\notin E(\overline{P_{n}})$. And for each $1\le m\le \frac{n-2}{2}$, all vertices of $\overline{P_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{P_{n}})$ and $v_{2m-1}v_{2m+1}\notin E(\overline{P_{n}})$.

By Definition 3.1, we note that

We find that except the above contributions corresponding three contributing sets, the sum of other contributions of $f^{+}$ is equal to $0$. Thus we obtain

Case 2. If $n$ is odd.

If $n$ is odd, then we assume that $v_{1}v_{2}\in E(\overline{P_{n}})$, $v_{1}v_{3}\notin E(\overline{P_{n}})$ and $v_{n-1}v_{n}\notin E(\overline{P_{n}})$. And for each $1\le m\le \frac{n-3}{2}$, all vertices of $\overline{P_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{P_{n}})$ and $v_{2m+1}v_{2m+3}\notin E(\overline{P_{n}})$.

By Definition 3.1, it holds that

We claim that except the above contributions corresponding three contributing sets, the sum of other contributions of $f^{+}$ is equal to $1$.

As a result, we have

We illustrate sum index labelings $f$ of $\overline{P_7}$ and $\overline{P_8}$, respectively (see Figure 6).

Next, we consider the difference index of $\overline{P_{n}}$. We have $d(\overline{P_n})\ge n-3$ by Property 1.4, which means that we just find a vertex labeling $g$ such that $\left| g^-\right| = n-3$ in the following. We distinguish two cases according to the parity of $n$.

Case 1. If $n$ is even.

Let $g:V(\overline{P_{n}})\to \mathbb{Z}$ be an injective labeling of $\overline{P_n}$ such that

for $1 \le i \le n$.

In this case, we assume that $v_{1}v_{2}\in E(\overline{P_{n}})$, $v_{n-5}v_{n-2}\notin E(\overline{P_{n}})$, $v_{n-4}v_{n-3}\notin E(\overline{P_{n}})$, $v_{n-3}v_{n}\notin E(\overline{P_n})$, $v_{n-2}v_{n-1}\notin E(\overline{P_n})$ and $v_{n-1}v_{n}\notin E(\overline{P_{n}})$. And for each $1\le m\le \frac{n-6}{2}$, all vertices of $\overline{P_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{P_{n}})$ and $v_{2m-1}v_{2m+1}\notin E(\overline{P_{n}})$.

According to Definition 3.1, we have

Since the sum of other contributions of $g^{-}$ is equal to $0$ excepting the above contributions.

As a result, it holds that

Case 2. If $n$ is odd.

Let $g:V(\overline{P_{n}})\to \mathbb{Z}$ be an injective labeling. For $1\le i \le n$, we define $g$ of $\overline{P_{n}}$ as

In this case, we assume that $v_{1}v_{2}\in E(\overline{P_{n}})$, $v_{1}v_{3}\notin E(\overline{P_{n}})$, $v_{n-5}v_{n-2}\notin E(\overline{P_{n}})$, $v_{n-4}v_{n-3}\notin E(\overline{P_{n}})$, $v_{n-3}v_{n}\notin E(\overline{P_n})$, $v_{n-2}v_{n-1}\notin E(\overline{P_n})$ and $v_{n-1}v_{n}\notin E(\overline{P_{n}})$. Note that all vertices of $\overline{P_n}$ satisfy $v_{2m}v_{2m+2}\notin E(\overline{P_{n}})$ and $v_{2m+1}v_{2m+3}\notin E(\overline{P_{n}})$ for each $1\le m\le \frac{n-7}{2}$.

Hence, according to Definition 3.1, it follows that

The sum of other contributions of $g^{-}$ is equal to $0$ excepting the above contributions corresponding two contributing sets.

As a result, we have

We illustrate difference index labelings $g$ of $\overline{P_7}$ and $\overline{P_8}$, respectively (see Figure 7). □

4.   Conclusions

In this article, we first obtain the properties of sum index labelings and difference index labelings. We also improve the sharp lower bounds on sum and difference indices of generalized regular graphs. In this regard, the sum indices and difference indices of the necklace graphs and the complements of matchings, cycles and paths are determined. Finally, we compare the sum indices with the (integral) sum numbers of several types of graphs and find that there are certain relationships in this section (see Table 1).

According to the sum indices and difference indices of regular graphs in this paper, the values of two invariants of a part of known regular graphs are listed in Table 2. Preliminary investigations on regular graphs lead us to the following conjecture.

Conjecture 4.1. If $G$ is $d$-regular, then $d(G) = d$.

Nowadays, the problems of the (integral) sum numbers have been studied comprehensively, while the problems of the sum and difference indices of graphs constitute challenges for researchers in graph labeling theory. Based on Table 1, we find that there exist certain relationships between the sum indices and the (integral) sum numbers of graphs. Of course, the current manuscript defines a starting point for the study of the sum and difference indices of regular graphs. However, a much deeper study is required to determine these two invariants of more graph families including regular graphs. Thus it would be interesting to find solutions to the questions below.

Problem 4.1. What are the specific relationships between the (integral) sum numbers and sum indices, or in what graphs do these relationships exist referring to Table 1?

Problem 4.2. As we all know, the generalized Peterson graphs have been extensively investigated as many nice structural and algorithmic properties. Determine the sum and difference indices of generalized Peterson graphs, which are 3-regular.

Problem 4.3. The torus grid graph is the graph formed from the Cartesian product $C_m \times C_n$ of the cycle graphs $C_m$ and $C_n$. Try to determine the sum and difference indices of torus grid graphs, which are 4-regular.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors are much grateful to the anonymous referees for their valuable comments on our paper, which have considerably improved the presentation of this paper. This work is supported by the 2022 Subject Development Research Fund Project of China University of Geosciences, Beijing and the 2023 Graduate Innovation Fund Project of China University of Geosciences, Beijing (Grant No. YB2023YC024).

Conflict of interest

All authors declare no conflict of interest that could affect the publication of this paper.