Graph theory, as discussed in [1], has experienced significant growth, particularly in the area of graph labeling. Gallian’s survey [2] highlights the progress that has been made in this field. One of the labeling methods that has emerged is graceful labeling. In 1966, Rosa [3] introduced the concept of graceful labeling, originally referred to as β-valuation. This method of labeling was subsequently termed graceful labeling by Golomb [4].

In a graph G with vertex set and edge set E(G), a graceful labeling f is an injective function , such that if we define , where | for every then w is a bijective function. A graph is classified as a graceful graph when a labeling of this type is possible.

Beutner and Harborth [5] established the criteria that fully determine whether a complete graph can be gracefully labeled. Further insights into which graphs are graceful have been provided by Eshghi [6], Zhou [7], and Dhami [8]. Kaneria et al. [9] explored graceful labelings in binary trees and regular trees. Additionally, Aldred et al. [10] conducted computational studies on the number of graceful labelings in path graphs. Gross and Yellen [11] compiled a list of graphs proven to be graceful, while Drake and Redl [12] examined graphs that are not graceftheoremul. Research on graceful labelings has continued to develop in various classes of graphs arising from algebraic structures. Recent studies have focused particularly on graphs constructed from groups. For instance, Sehgal et al. investigated graceful labelings of power graphs of the group [13], and further extendedtheir work to prime index graphs of the group [14]. In addition, Kumari et al. explored super graceful labelings of comaximal subgroup graphs derived from the cyclic group [15]. These studies demonstrate a growing interest in establishing graceful labelings on graphs motivated by algebraic properties.

Ahmed et al. [16, 17] introduced a novel labeling technique called graceful antimagic labeling. In this scheme, a injective function (graceful labeling) assigns diferent values to the vertices of a graph where the labels are taken from the set . The corresponding edge labeling , determined by for each edge , must fulfill the following conditions: for any two diferent edges,

(1) the edge labels must be distinct, meaning that is a graceful labeling; and (2) for any two diferent vertices , where

This implies that is also an antimagic labeling. In this case, the labeling is called a graceful antimagic labeling.

Inspired by the concepts of graceful labeling and vertex irregular total labeling described by Ahmad and Baˇca [18], we define a new labeling, called graceful vit labeling. A graceful labeling f on graph is called as a graceful vit labeling if for any , where

In this case, to simplify the notation, given a graceful labeling f on a graph , the induced edge label from the graceful weight is denoted by | for every . Then, the graceful vit weight of each vertex is defined as . Thus, a graceful labeling on a graph G is called a graceful vit labeling if for every two diferent vertices , it holds that . Furthermore, a graph G is called a graceful vit graph if it admits a graceful vit labeling. A graceful vit labeling extends the idea of graceful labeling by adding the condition that the vertex weight values for any two distinct vertices must also be distinct. Although this condition is similar to that in graceful antimagic labeling, the key diference lies in how vertex weights are defined. In graceful vit labeling, the weight of a vertex is calculated by summing the vertex’s graceful label and the weights of all edges incident to that vertex, derived from graceful labeling. This definition of vertex weight aligns with the definition of vertex weight in total irregular vertex labeling. Apparently, not all graceful labels are also graceful vit, as shown in Figure 1. The labeling shown in the first graph meets the criteria for a graceful labeling but does not qualify as a graceful vit labeling. In contrast, the second graph exhibits a labeling that satisfies the graceful vit condition. To enhance clarity, the corresponding edge labels are displayed, and the vertex weights (indicated in red) are also presented.

This study focuses on examining the concept of graceful vitness—the characteristic of admitting a graceful vit labeling—across a variety of graph classes. Specifically, we examine the graceful vitness of nearly complete graphs, certain families of trees, cycles, and wheel graphs. By focusing on these graph structures, we aim to deepen the understanding of how graceful vit labeling can be applied and identify the conditions under which it is possible.

This investigation builds on the foundational ideas of graceful, graceful antimagic, and vertex irregular total labelings discussed in previous works. By integrating these concepts, we extend the study of labeling techniques and provide a new perspective on their applicability to well-known graph families. Our findings contribute to the growing body of literature on graph labeling and uncover new connections between graph structure and labeling properties.

This section opens with a fundamental result concerning graceful vit labelings of complete graphs. The subsequent theorem establishes criteria for a complete graph to possess a graceful vit labeling, depending on how many vertices it contains.

Theorem 2.1.A complete graph admits a graceful vit labeling if and only if n = 1, 2, or 4.

Proof. Golomb [4] established that a complete graph is a graceful graph if and only if . Using this result, we determine which of these graphs also satisfy the conditions for being a graceful vit graph.

First, it is straightforward to verify that is a graceful vit graph since it trivially satisfies all labeling conditions. For and , we provide examples of graceful vit labelings, as illustrated in Figure 2. Given an injective function and with and , we obtain the induced edge labels

Since all edge labels in and all edge labels in are distinct, both f and are graceful labelings. Furthermore, the graceful vit weights of the vertices are computed as follows:

Thus, all vertices of each graph have distinct weights, and therefore both and g are graceful vit labelings. In both cases, the vertex weights derived from these labelings are distinct for all vertices, confirming that these graphs are graceful vit graphs.

After that, we consider , with vertices and considering graph isomorphism, has exactly two distinct graceful labelings. Table 1 displays these labelings along with their induced vertex weights.

In both cases, the vertex weights are not distinct, violating the conditions for graceful vit labeling. Therefore, is not a graceful vit graph. From this analysis, we conclude that the only complete graphs that admit graceful vit labelings are , and □

Theorem 2.1 reveals that the graceful vit property is exclusive to complete graphs with a limited number of vertices—namely, , and . It underscores the inherent restrictions on the applicability of graceful vit labelings in complete graphs, indicating that larger complete graphs fail to meet the stringent conditions required for this labeling. Building on the theorem, which characterizes the graceful vit property for complete graphs we now extend our discussion to the graphs formed after deleting one edge from a complete graph. Specifically, we examine the graph which is derived by eliminating one edge from the complete graph The next theorem investigates the graceful vitness of these modified graphs, establishing the conditions under which admits a graceful vit labeling.

Theorem 2.2.The graph is a graceful vit graph if and only

Proof. According to Beutner and Harborth [5], the graphs admits a graceful labeling if and only if . This implies that the graph with 5 \end{document} ]]> is not a graceful graph. Since every graceful vit graph is also a graceful graph, it follows that with 5 \end{document} ]]> is not a graceful vit graph either. In the graphs , and , graceful vit labelings are provided in Figure 3.

Theorem 2.2 highlights a key diference in the graceful vit labeling of complete graphs and their edge-deleted counterparts. While only , and can be graceful vit graphs as complete graphs, the removal of a single edge from opens up the possibility for , and to be graceful vit graphs. This suggests that removing an edge from a complete graph can relax some of the stringent conditions required for a graceful vit labeling, allowing for a broader range of graphs to satisfy the labeling criteria.

Thereafter, we focus on a particular class of graphs called star graphs. A star graph is formed by one central vertex connected directly to n surrounding vertices. In this case, we investigate the graceful vit labeling property of star graphs. The next theorem provides a result regarding the graceful vit graph nature of star graphs for diferent values of

Theorem 2.3. For any positive integer n , the star graph is a graceful vit graph and only .

Proof. It is observed that the star graph is isomorphic to . According to Theorem 2.1, the graph is a graceful vit graph. Subsequently, the star graph is isomorphic to the graph . According to Theorem 2.2, it follows that the graph is a graceful vit graph. Consider the star graph with . Let

Let the vertex labeling be defined by assigning for each . Note that for

For any , where , which means , we have . Thus, h and are injective functions. Hence, h is a graceful labeling. Furthermore, compute the weight of each vertex in under the labeling h and as follows.

We know that . Since , we have 2 \end{document} ]]> and

Consequently, we get . Thus, is an injective function. Therefore, there exists a function h that is a graceful vit labeling, and hence the star graph with is a graceful vit graph. Now, let us consider the illustration of the star graph

Suppose there exists a graceful vit labeling . To get an edge weight of 3, we must have or . If , then without loss of generality, we can take , and . In this case, we have

This brings about a contradiction, since g is supposed to be a graceful vit labeling. On the other hand, if , then we have g ( v _ { j } ) \end{document} ]]> for . Note that

These results contradict the fact that g is a graceful vit labeling. Hence, the assumption must be false. Therefore, the star graph is not a graceful vit graph.

In this section, we examine the graceful vit graph property of path graphs. A path graph is a simple graph where each vertex is connected to at most two other vertices. The next lemma shows that the path graph , which consists of four vertices, does not possess the graceful vit graph property.

Lemma 2.4. The path graph is not graceful vit.

Proof. Given the path with vertex set and edge set , it can be readily verified that considering isomorphism, there are just two distinct graceful labelings of the path

Since the resulting vertex weights are not unique, we conclude that the path is not a graceful vit graph. □

In [3], it is demonstrated that a path is graceful for all . However, according to Lemma 2.4, the path is not graceful vit. For ， the corresponding graceful vit labels are as follows.

For larger values of a general formula for the number of graceful labelings of paths remains elusive. However, Aldred et al. [10] showed that for suficiently large the number of graceful labelings of paths exceeds . Given the results discussed above, we are led to propose the following conjecture.

Conjecture 1.For every integer and , the path admits a graceful vit labeling.

We now turn our attention to cycle graphs. Although cycle graphs are known to have interesting properties in the context of graceful labelings, it turns out that the cycle graphs and do not satisfy the conditions for being graceful vit graphs. This can be formally stated as follows.

Lemma 2.5.The cycle graphs and are not graceful vit graphs.

Proof. To investigate the graceful vit labeling of cycle graphs, we first consider the cycle graph . Since , using Theorem 2.1, we know that is not graceful vit.For the cycle graph defined by the vertex set and the edge set There are only two possible graceful labelings of up to isomorphism.

We note that in both cases the induced vertex weights are not unique. Therefore, the cycle graph fails to be a graceful vit graph. Hence, we conclude that both and are not graceful vit graphs.

In [3], it is proved that a cycle is graceful if and only if (mod 4) or . Based on Lemma 2.5, the graphs and are not graceful vit graphs. For and , the corresponding graceful vit labels are as follows.

For larger a general formula could not be determined. Therefore, we present the following open question.

Open Problem 1.Determine the properties of graceful vit labelings for cycle graphs with where (mod 4) or (mod 4).

In this section, we analyze the structure of double star graphs and their graceful vit labeling properties. A double star graph consists of two central vertices connected by an edge, where one central vertex is adjacent to n leaf vertices and the other is adjacent to m leaf vertices. In Theorem 2.6, we provide conditions under which such graphs can be graceful vit graphs.

Theorem 2.6.The double star graph is a graceful vit graph and only if n = 1 and m or and

Proof. Consider the double star graph with . For the graph is isomorphic to the graph . According to Lemma 2.4, the graph is not a graceful vit graph. Note that the graph is isomorphic to the graph . Without loss of generality, consider the double star graph ,m with . First, let

and

Define the vertex labeling function such that for every , we have

Since , we get injective. Furthermore, for

and

Since , we get injective and thus is a graceful labeling. We now compute the weight of each vertex in under the labeling and as follows.

For we have

Consider that

Since 0 , } \end{array} \end{document} ]]> , we get

Thus, . Hence, the weight function is injective, demonstrating the existence of a function that provides a graceful vit labeling. Consequently, the double star graph with is a graceful vit graph.

Now, consider the double star graph where . Let

and

In this graph, and are the central vertices, while the vertices and (with and represent the leaves. Suppose there is a graceful vit labeling function on . If a central vertex has a label greater than at least two labels on its leaves, for example, if g ( a _ { 1 } ) \end{document} ]]> and g ( a _ { 2 } ) \end{document} ]]> ), then we get the following weight calculations:

10

and

This will lead to a contradiction with the fact that is a graceful vit labeling. On the other hand, since is a graceful labeling, labels 0 and must be labels of two adjacent vertices. Examine two separate cases as follows.

Case 1. If there exists such that , then This leads to for resulting in a contradiction. Similarly, if there exists such that , then . This leads to for resulting in a contradiction.

Case 2. If , then we have or for some . If , then for resulting in a contradiction. To simplify the argument, let us consider . Then, to get edge weight of it can only be formed from labels 0 and or from labels and 1. Since vertex has order 1, we get . Similarly, we get . Then, to get an edge weight of , we must have . This leads to for , resulting in a contradiction.

Similarly, if , then we have for some . If g(xa) = n + m + 1, then for , resulting in a contradiction. To simplify the argument, let us consider . Then, to get an edge weight of it can only be formed from labels 0 and or from labels 1 and Since vertex has order 1, we get . Similarly, we get . Then, to get an edge weight of , we must have . This leads to untuk , resulting in a contradiction.

Based on the analysis of Cases 1 and 2, we reach a contradiction, as both cases lead to inconsistencies with the assumption that is a graceful vit labeling. Therefore, it follows that the double star graphs with cannot be graceful vit graphs. □

Let the generalized star graph be a graph that consists of one central vertex u connected to n vertices and each is connected to another vertex . This creates a structure where u is the central vertex, and each is connected to its corresponding leaf . The edge set of this graph is:

Now, we turn our attention to the graceful vit labeling of the generalized star graph for . The following theorem demonstrates that this graph is indeed a graceful vit graph for these values of n.

Theorem 2.7.The generalized star graph is a graceful vit graph for every positive integer

Proof. Given the star graph with , first, let

For odd a labeling of points is defined as

such that , and for every

For every . Observe that and each (for are assigned odd values, while and are even numbers for every . Since

and

we get is an injective function. Subsequently, we observe the edge weights of the graph

for

Note that f ^ { * } ( u x _ { 1 } ) > f ^ { * } ( u x _ { 2 } ) > f ^ { * } ( u x _ { 3 } ) > \cdots > f ^ { * } ( u x _ { n } ) \end{document} ]]> . On the other hand, for f ^ { * } ( x _ { i } y _ { i } ). \end{document} ]]> Assuming that there exist and such that , we get

which leads to a contradiction. Assume there exist where and such that , we get

resulting in a contradiction. Assume there exist and such that , we get

Contradiction. Thus, is injective and it follows that is a graceful labeling. In the following, we calculate the weight of each vertex in under the labeling f and as follows. For we have

For , we have

and

For we have

Note that the values of and for every are odd numbers. For , we have

On the other hand, for every , while (mod 4) for every . The values and are even numbers. Observe that for

and

For , we have w _ { f } ( x _ { 1 } ) > w _ { f } ( u ) \end{document} ]]> , hence is an injective function.

For and , the given labelings in Figures 5 are graceful vit labelings. Thus, the star graph with is a graceful vit graph.

For 5 , \end{document} ]]> we have not succeeded in identifying a general formula. Therefore, we present the following open problem.

Open Problem 2. Find the properties of graceful vit labelings for generalized star graphs with 5. \end{document} ]]>

In addition to star graphs, double star graphs, and generalized star graphs, we are also exploring graceful vit labeling in another type of tree graph, specifically complete binary tree graphs.

Lemma 2.8.The complete binary tree graph is not a graceful vit graph.

Proof. The complete binary tree graph can be illustrated as shown in Figure 6.

Let assume there exists a graceful vit labeling Suppose for some and , then the analysis can be divided into the following three cases.

Case 1. If , then or . It is observed that if then and , resulting in vertex weights

This is impossible since g is a graceful vit labeling. Analogously, for the case , it follows that , leading to a contradiction with g being a graceful vit labeling.

Case 2. If , then . Analogously, this results in a contradiction as in Case 1.

Case 3. If , then or or . If then and , resulting in vertex weights

This causes a logical inconsistency since g is a graceful vit labeling. Furthermore, if , then or . If , then and . In this case, a contradiction is obtained using a similar approach as in the case . On the other hand, if , then . This implies that and . Hence, by applying a similar argument as in the previous cases, we obtain a contradiction.

Based on Cases 1, 2, and 3, a contradiction is always obtained with the fact that g is a graceful vit labeling. Thus, the assumption must be false. Therefore, the graph is not a graceful vit graph. □

After that, we examine the graceful vit labeling on wheel graphs. A wheel graph consists of a cycle of n vertices with an additional central vertex connected to all vertices in the cycle. In this section, we aim to demonstrate that can be labeled gracefully as a vit graph for every odd . The following theorem formalizes this result.

Theorem 2.9.The wheel graph is a graceful vit graph for every odd number

Proof. Given the wheel graph with n being an odd number and . First, let

and

Moreover, a labeling of the vertices can be defined such that for every vertex in the graph

and

Since we get f is an injective function. Furthermore, the edge weights of the edges of can be determined as follows. For each edge in the graph we obtain,

Observe that the values of , and for are all odd integers. On the other hand, , and for are even numbers. Therefore,

Since is injective, we get is a graceful labeling. Furthermore, the weight of each vertex in under the labeling and can be computed as follows. For , we have

For have

Note that and

For w _ { f } ( v _ { i } ) \end{document} ]]> for every . Assuming , we have

Moreover, it can be shown that the vertex weights in the wheel graph are all unique. Assuming , we get For , we have

If there exists such that , then

creating a contradiction since is odd. Assuming , we get

If there exists such that , we have

yielding an inconsistency because is odd. Assuming , we get

If there exists such that , then

yielding an inconsistency since is odd.

For the labeling given in Figure 7 is a graceful vit labeling.

Thus, it is shown that the function is injective, meaning that f is a graceful vit labeling. In conclusion, the wheel graph with an odd number is a graceful vit graph. □

This paper presents a novel concept of graceful labeling, which we call ”graceful vit labeling.” In this approach, for every couple of vertices that are not the same, the vertex weight values must be diferent. The weight assigned to a vertex is calculated by adding its graceful label to the total weights of all edges connected to it in a given graceful labeling. For a graph to qualify as graceful vit, it is required that the graph is graceful in the first place. Through our analysis, we identified several connected graphs—including , and (where —that are graceful but not graceful vit. This observation raises an interesting question about the generality of this property, and we propose the following open problem:

Open Problem 3. Can we describe the entire class of graphs that are graceful yet not graceful vit?