Rosa [1] defined a β-valuation of a graph G with n edges as an injective mapping such that, when the label | is assigned to the edge , the resulting edge labels are distinct. The term graceful labeling for this valuation was later coined by Golomb [2], and this terminology has since become the standard in the literature.

The problem of classifying graphs as graceful or otherwise has sparked extensive research endeavors by numerous researchers, yielding a substantial body of work in this fascinating area. A detailed overview of various labeling techniques, including the graceful labeling, has been presented in [3].

The concept of directed power graphs was introduced in [4] for groups and was subsequently extended to semigroups in [5, 6]. “The directed power graph of a group G is the graph with vertex set and edge set The underlying undirected power graph is the graph with vertex set G in which two distinct vertices are adjacent if and only if one is a power of the other.”

In [7, 8, 9] , the authors carried out a detailed study of undirected power graphs, revealing many of their structural and combinatorial properties. Subsequent works have investigated several graph-theoretic parameters associated with power graphs and their variants, such as diameter, domination number, coding properties, and metric dimensions; see, for example, [10, 11, 12, 13].

These developments have naturally led to the study of graceful labelings of power graphs of finite groups. Abawajy et al. [14] provided an extensive survey of results on power graphs available in the literature. They also discussed various conjectures, open questions, and research problems proposed by other authors, including the problem of identifying groups and semigroups whose undirected power graphs admit graceful labelings. In 2022, the authors in [15] established a graceful labeling of the power graph of the group

In this paper, we investigate power graphs of certain finite groups and classify them as graceful or non-graceful. Our results further illustrate the connection between algebraic structures and graph labeling theory. Throughout the paper, all power graphs considered are undirected.

For completeness, we recall some well-known results that will be used later.

Theorem 1.1 ([1]). is an Eulerian graph with n edges, where (mod 4) (mod 4), then there does not exist a β-valuation of the graph

Theorem 1.2 ([2]). “If 4 \end{document} ]]> , then the complete graph can not be graceful.”

Theorem 1.3 ([7]). “Let G be a finite group. Then is complete if and only if G is a cyclic group of order 1 or , for some prime number p and some m "

The key results of our study are presented below. We begin by establishing the gracefulness of the finite abelian group . Subsequent results address other classes of finite groups and their associated power graphs.

Theorem 2.1.The power graph of is graceful for , 3 and for all

Proof. For , the power graph of consists of vertices of order two and a single vertex of order one, namely the identity element e. Further, e is adjacent to all other vertices, and no edges exist among the remaining vertices. We assign labels to the vertices as mentioned in the following table:

Thus, the induced edge labels are 1 ; consequently, is graceful in this case.

For , every non-identity vertex of has order 3. Moreover, the structure of the power graph of coincides with the windmill graph

As an illustration, consider the power graph of the group \times < y > \end{document} ]]> shown in Figure 1. It is isomorphic to the windmill graph

It can be readily verified that, for 1 (mod 4).

Hence, the desired result follows from the fact that the windmill graph is graceful whenever or 1 (mod 4) (see [16]).

Theorem 2.2.Let G be a finite non-trivial group of order . Then the power graph of G is graceful unless

Proof. We proceed by considering the following cases.

Case I:

In this case, , and by Theorem 1.3 we have . It can be readily checked that is graceful.

Case II:

Up to isomorphism, there are two groups of order four: the cyclic group and the Klein four-group . Hence, either If , then is graceful, as shown in [15].

If , then by Theorem 2.1, the power graph of G is graceful.

Case III:

Then G must be isomorphic to either or (the dihedral group of order 6), since these are the only two groups of order 6 up to isomorphism.

Subcase

Let . Define a function by

Then Φ is a graceful labeling of the power graph of G (see Figure 2).

Subcase B:

Let us take

Define a function Ψ by

Then Ψ provides a graceful labeling of the power graph of as illustrated in Figure 3.

Case IV:

In this case, G has prime order and hence is cyclic. By Theorem 1.3, P(G) is a complete graph, and therefore, by Theorem 1.2, it is not graceful.

Consequently, all non-trivial groups of order at most 7 yield graceful power graphs, except for orders 5 and 7.

Theorem 2.3.Let G be a finite group of order . Then the power graph of G is graceful unless G is isomorphic to the cyclic group

Proof. We establish the theorem by analyzing the possible group structures corresponding to the two values of n separately.

Case I:

In this case, G is isomorphic to one of the following five groups:

where denotes the dihedral group of order 8 and denotes the quaternion group of order 8. We consider the following subcases.

Subcase A: , then the result follows from Theorems 1.2 and 1.3.

Subcase B: If , let

The vertex and edge labeling of shown in Figure 4 is graceful, which establishes the result in this case.

Subcase C: If , then it has been shown in [15] that the power graph admits a graceful labeling.

Subcase D: If , then P(G) is graceful by Theorem 2.1.

Subcase E: If , let

Define Ω : by

The vertex labeling defined by Ω together with the induced edge labeling of is illustrated in Figure 5. This labeling is graceful, and hence the theorem holds in this case.

Case II:

Since there are only two groups of order 9 up to isomorphism, namely and , it follows that G is isomorphic to one of these two groups.

If then proceeding as in Subcase A of Case I, the power graph is not graceful. On the other hand, if , then by Theorem 2.1, the power graph is graceful.

The result now follows by combining the conclusions of Case I and Case II. □

Theorem 2.4.If p and q are odd prime numbers such that or 7 (mod 8), then the power graph of is not graceful.

Proof. Let . The distinct vertices of the power graph , together with their corresponding degrees, are listed in Table 2.

The total number of edges of the power graph is given by

where denotes Euler’s totient function.

Since p and q are odd primes, both and are even. Consequently,

We now consider the following cases.

Case 1: If (mod 8), then from it follows that

Case 2: If (mod 8), the same expression yields

Moreover, Table 2 shows that every vertex of has even degree. Hence is an Eulerian graph. Consequently, by Theorem 1.1, the power graph of cannot be graceful. □

Theorem 2.5. Let

where . Then the power graph is graceful.

Proof. The following observations about the group G are noteworthy:

• The group has elements, of which only the identity element e has order one.

• There are elements of the form

each of order 2. We denote these elements by , where

• Apart from the identity, there are elements of the form

where the exponents ’s are not all zero simultaneously. These elements have order 3 and can be partitioned into pairs , where each pair consists of an element and its square.

• Consequently, the number of cyclic subgroups of order 3 is and these subgroups are precisely

The components of the power graph are described as follows.

• The vertex set of the graph is

• For each element of order 2, the inclusion , gives rise to edges.

• In each cyclic subgroup of order

the relations

imply that the pairs and are adjacent in . Hence

these subgroups contribute edges in total.

• There are no other edges in beyond those described above.

• Hence the total number of edges of is

Consequently, the structure of the power graph of the finite non-abelian group G can be written as

sWe define a labeling

as follows:

Table 3 and Table 4 display the edge labels induced by ℧ for even and odd values of respectively.

It is evident from the two tables that the induced edge labels are

Consequently, the labeling ℧ is a graceful labeling of the power graph , which completes the proof.

The labeling scheme described above is illustrated in Figure 6, which represents the power graph of the group

The figure displays both the graceful vertex labeling and the induced edge labeling. The structure of this power graph is

In this paper, we have investigated the graceful labeling of power graphs associated with finite groups. Our study has led to a classification of these graphs as either graceful or non-graceful. In particular, we analyzed power graphs of finite groups of order up to 9.

Furthermore, we identified two distinct classes of finite groups: one consisting of cyclic groups whose power graphs do not admit graceful labeling, and the other comprising certain non-abelian groups whose power graphs are graceful. These results highlight the influence of algebraic properties of groups on graph labeling behavior.

We hope that this perspective will stimulate further research on labeling problems in algebraic graph theory and encourage the study of power graphs of larger and more general classes of groups.