Tita Khalis Maryati^a , Fawwaz Fakhrurrozi Hadiputra^b , A. N. M. Salman^b

^aDepartment of Mathematics Education, Universitas Islam Negeri Syarif Hidayatullah Jakarta, Indonesia ^bCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

tita.khalis@uinjkt.ac.id, fawwazfh@alumni.ui.ac.id, msalman@math.itb.ac.id

Let G be a simple, finite, and undirected graph and H be a subgraph of G. The graph G admits an H-covering if every edge in G belongs to a subgraph isomorphic to H. A bijection f : V (G) ∪ E(G) → [1, n] is a magic total labeling if for every subgraphs H′ isomorphic to H, the sum of labels of all vertices and edges in H′ is constant. If there exists such f, we say G is H-magic. A graph F is said to be a forbidden subgraph of H-magic graphs if F ⊆ G implies G is not an Hmagic graph. A set that contains all forbidden subgraph of H-magic is called forbidden family of H-magic graphs, denoted by F(H). In this paper, we consider F(Ph), where P^h is a path of order h. We present some sufficient conditions of a graph being a member of F(Ph). Besides that, we show the uniqueness of a minimal tree which belongs to F(P3) and characterize P3-(super)magic trees.

Keywords: Magic labeling, covering, paths, trees Mathematics Subject Classification : 05C78, 05C05

DOI: 10.5614/ejgta.2024.12.1.5

1. Introduction

Let G and H be finite, simple, undirected graphs. We write G admits an H-covering if every edge in the graph belongs to a subgraph H′ which is isomorphic to H. The graph G is called H-magic if G admits H-covering and there exists total labeling f : V (G) ∪ E(G) → [1, |V (G)| + |E(G)|] such that there exists positive integer k which w(H′ ) = P v∈V (H′) f(v)+P e∈E(H′) f(e) =

Received: 2 July 2022, Revised: 26 November 2023, Accepted: 10 December 2023.

k, for each subgraph H′ ∼= H of G. Furthermore, if f also have extra property f(V (G)) = [1, |V (G)|], then G is H-supermagic. A special case of K2-supermagic graphs is called edgesupermagic graphs. Some results concering H-(super)magic graphs can be seen in [1], [5], [9]. For more information about (super)magic labeling and its variations, readers may consult to [3].

A graph F is called a forbidden subgraph of H-magic if F ⊆ G implies G is not H-magic. Let F(H) be a set containing every graph admitting H-covering which is not allowed to be a subgraph of any H-magic graph. We call such set as forbidden family F(H). Known studies about forbidden subgraph in magic labeling may be seen in [4], [6], [7], [8]. We adopt these results in our notation.

Theorem 1.1. [4] Let h ≥ 3 be positive integer. We have C^h ∈ F(Ph).

A (n, k)-tadpole is a graph constructed by identifying an end vertex of P^k with a vertex of Cn. Maryati et al. [7] write C +1 n ∼= (n, 1)-tadpole.

Theorem 1.2. [7] Let h ≥ 4 be positive integer. We have {C +1 h−1 , C+1 ^h+1} ⊆ F(Ph).

Moreover, Maryati et al. [6, 7] defined Hⁿ graph with a vertex and edge set

\[V(H_n) = \{v_{1,i}, v_{2,i} \mid i \in [1, 2n+1]\},\]
\[E(H_n) = \{v_{1,i}v_{1,i+1}, v_{2,i}v_{2,i+1} \mid i \in [1, 2n]\} \cup \{v_{1,n+1}v_{2,n+1}\}.\]

They determined that this graph is also a forbidden subgraph of Ph.

Theorem 1.3. [6, 7] Let h ≥ 3 be positive integer. We have H^h ∈ F(Ph).

This paper is written as follows. In Section 2 and 3 we investigate sufficient conditions for a graph which belongs to F(Ph). Section 2 mainly deals with tree graphs, while Section 3 deals with unicyclic graphs. Furthermore, we found that there is no tree other than H¹ which belongs to F(P3) of small order in Section 4.

2. Trees in F(Ph)

We define Dt(v, u) as a set of every length of possible paths formed with endpoints of v, u. Clearly, d(v, u) ∈ Dt(v, u) and for u, v vertices in trees we have Dt(v, u) = {d(v, u)}. To start, two supplementary lemmas are provided which arose from the implications of graphs being Phmagic. The first lemma tells us that some parts in every paths having length more than h in a graph will induce constant sums.

Lemma 2.1. Let n ≥ 3, m ∈ [1, ⌊ n−1 2 ⌋] be integers. Let G be a graph that has f as a Ph-magic labeling of G. If there exists u, v ∈ V (G) with n ∈ Dt(u, v), then there exists consecutive vertices x0, x1, ..., x^m = u and y0, y1, ..., y^m = v such that

\[\sum_{i=1}^{m} f(x_i) + \sum_{i=1}^{m} f(x_{i-1}x_i) = \sum_{i=1}^{m} f(y_i) + \sum_{i=1}^{m} f(y_{i-1}y_i).\]

Proof. Since n ∈ Dt(u, v), then there exists consecutive vertices u = z1, z2, z3, ..., zn+1 = v. By taking weights of two subgraphs from consecutive vertices z1, z2, ..., zn−m+1 and zm+1, zm+2, ..., zn+1 we have

\[\sum_{i=1}^{n-m+1} f(z_i) + \sum_{i=2}^{n-m+1} f(z_{i-1}z_i) = \sum_{i=m+1}^{n+1} f(z_i) + \sum_{i=m+2}^{n+1} f(z_{i-1}z_i),\]

which implies

\[\sum_{i=1}^{m} f(z_i) + \sum_{i=2}^{m+1} f(z_{i-1}z_i) = \sum_{i=n-m+2}^{m+1} f(z_i) + \sum_{i=n-m+2}^{m+1} f(z_{i-1}z_i).\]

substituting xⁱ = zm−i+1 and yⁱ = zn−m+i+1 we got the result as desired.

Next, constant sums may also appear in parts of a subgraph isomorphic to a certain tree with three pendants.

Lemma 2.2. Let n ≥ 3, m ∈ [ n+1 2 , n−1] be integers. Let G be a graph that has f as a Ph-magic labeling of G. If there exists four vertices x1, w, y, z such that

• 1. there exists m satisfying m ∈ Dt(w, y) and m ∈ Dt(w, z),
• 2. there exists n satisfying so that m + n ∈ Dt(x1, y),

then there exists a consecutive vertices x1, x2, ..., xⁿ = w, v1, v2, ..., v^m = y and x1, x2, ..., xⁿ = w, u1, u2, ..., u^m = z such that

\[\sum_{i=1}^{m} f(v_i) + \sum_{i=1}^{m} f(v_{i-1}v_i) = \sum_{i=1}^{m} f(u_i) + \sum_{i=1}^{m} f(u_{i-1}u_i)\]

with xⁿ = v⁰ = u0.

Proof. By taking two subgraph of consecutive vertices x1, ..., xn, v1, ..., v^m and x1, ..., xn, u1, ..., u^m we got

\[\sum_{i=1}^{n} f(x_i) + \sum_{i=1}^{n-1} f(x_i x_{i+1}) + \sum_{i=1}^{m} f(v_i) + \sum_{i=1}^{m} f(v_{i-1} v_i)\] \[= \sum_{i=1}^{n} f(x_i) + \sum_{i=1}^{n-1} f(x_i x_{i+1}) + \sum_{i=1}^{m} f(u_i) + \sum_{i=1}^{m} f(u_{i-1} u_i).\]

This implies

\[\sum_{i=1}^{m} f(v_i) + \sum_{i=1}^{m} f(v_{i-1}v_i) = \sum_{i=1}^{m} f(u_i) + \sum_{i=1}^{m} f(u_{i-1}u_i),\]

therefore the lemma holds.

One kind of a graph belonging to F(Ph) is a new class of graph namely Tiara graphs. We define a Tiara graph G = T in(p, q, r) as follows

\[V(G) = \{v_i \mid i \in [1, (n-1)(q+1)+1]\} \cup \{x_{b,j} \mid b \in \{1, (n-1)(q+1)+1\}, j \in [1, r]\}\] \[\cup \{w_{(q+1)k+1,l} \mid k \in [0, n-1], l \in [1, p]\},\] \[E(G) = \{v_i v_{i+1} \mid i \in [1, (n-1)(q+1)]\}\] \[\cup \{v_b x_{b,1}, x_{b,j} x_{b,j+1} \mid b \in \{1, (n-1)(q+1)+1\}, j \in [1, r-1]\}\] \[\cup \{v_{(q+1)k+1} w_{(q+1)k+1,l}, w_{(q+1)k+1,l} w_{(q+1)k+1,l+1} \mid k \in [0, n-1], l \in [1, p-1]\}.\]

An example of T i4(1, 1, 3) is depicted in Figure 1. Theorem 2.1 and Theorem 2.2 deals with tiara graphs which belongs to F(Ph).

Theorem 2.1. Let h, s be positive integers with s ≥ 2. For every s being a solution of h(s), the following statements are true.

• a) If h = 2s + 1, then T i2(s, s − 1, s) ∈ F(Ph).
• b) If h = 2s, then T i2(s − 1, s − 1, s) ∈ F(Ph).

Proof. Let h be fixed. To prove part a) and b) simultaneously we set G ∼= T i2(h − s − 1, s − 1, s). Suppose G is Ph-magic with f as a Ph-magic labeling for G. In this proof, define w1,⁰ = v¹ and ws+1,⁰ = vs+1. Consider x1,s, v1, vh−s, w1,h−s−1. Notice that h − s − 1 ∈ Dt(v1, vh−s), h−s−1 ∈ Dt(v1, w1,h−s−1) and (h−s−1) + s = h−1 ∈ Dt(x1,s, vh−s). Therefore, by Lemma 2.2 we have

\[\sum_{i=2}^{h-s} f(v_i) + \sum_{i=2}^{h-s} f(v_{i-1}v_i) = \sum_{i=1}^{h-s-1} f(w_{1,i}) + \sum_{i=1}^{h-s-1} f(w_{1,i-1}w_{1,i}).\] (1)

Next, consider w1,h−s−¹ and ws+1,h−s−1. Since 2h−s−2 ∈ Dt(w1,h−s−1, ws+1,h−s−1), by Lemma 2.1 (setting m = h − s − 1) we have

\[\sum_{i=1}^{h-s-1} f(w_{1,i}) + \sum_{i=1}^{h-s-1} f(w_{1,i-1}w_{1,i}) = \sum_{i=1}^{h-s-1} f(w_{s+1,i}) + \sum_{i=1}^{h-s-1} f(w_{s+1,i-1}w_{s+1,i}).\] (2)

Then, consider xs+1,s, vs+1v2s+2−h, ws+1,h−s−1. Notice that h − s ∈ Dt(vs+1, v2s+2−h), h − s ∈ Dt(vs+1, ws+1,h−s−1) and (h − s) + s = h ∈ Dt(xs+1,s, vs+1). Therefore, by Lemma 2.2 we have

\[\sum_{i=1}^{h-s-1} f(w_{s+1,i}) + \sum_{i=1}^{h-s-1} f(w_{s+1,i-1}w_{s+1,i}) = \sum_{i=2s+2-h}^{s} f(v_i) + \sum_{i=2s+s-h+1}^{s+1} f(v_{i-1}v_i).\] (3)

From (1), (2) and (3), we have

\[\sum_{i=2}^{h-s} f(v_i) + \sum_{i=2}^{h-s} f(v_{i-1}v_i) = \sum_{i=2s+2-h}^{s} f(v_i) + \sum_{i=2s+2-h+1}^{s+1} f(v_{i-1}v_i).\]

If h = 2s + 1, this would imply f(v1) = f(vs+1). On the other hand, h = 2s implies f(v1v2) = f(vsvs+1). The contradictions of injectivity of f in both cases are implying T i2(h−s−1, s−1, s) ∈ F(Ph).

Theorem 2.2. Let h, s, t be positive integers. For every pair s, t being a solution of h = s(t+3)+1, then

\[Ti_{(t+3)}(s, s-1, s(t+2)) \in \mathcal{F}(P_h).\]

Proof. Let h be fixed. Suppose G ∼= T i(t+3)(s, s − 1, s(t + 2)) is Ph-magic with a magic labeling f. In this proof, define xk,⁰ = v^k = wk,⁰ for every k ∈ [1, h − s] (note that h − s = (t + 2)s + 1). First, consider vh−s, v1, x1,s, w1,s. Notice that s ∈ Dt(v1, x1,s), s ∈ Dt(v1, w1,s) and s+s(t+ 2) = s(t + 3) ∈ Dt(vh−s, x1,s). Hence, by Lemma 2.2, we have

\[\sum_{i=1}^{s} f(x_{1,i}) + \sum_{i=1}^{s} f(x_{1,i-1}x_{1,i}) = \sum_{i=1}^{s} f(w_{1,i}) + \sum_{i=1}^{s} f(w_{1,i-1}w_{1,i}).\] (4)

Then, considering w1,s and wh−s,s with s(t + 4) ∈ Dt(w1,s, wh−s,s) by Lemma 2.1 (setting m = s) we have

\[\sum_{i=1}^{s} f(w_{1,i}) + \sum_{i=1}^{s} f(w_{1,i-1}w_{1,i}) = \sum_{i=1}^{s} f(w_{h-s,i}) + \sum_{i=1}^{s} f(w_{h-s,i-1}w_{h-s,i}).\] (5)

Next, consider v1, vh−s, xh−s,s, wh−s,s. We can see that s ∈ Dt(vh−s, xh−s,s), s ∈ Dt(vh−s, wh−s,s) and s + s(t + 2) = s(t + 3) ∈ Dt(v1, vh−s,s). Therefore, by Lemma 2.2 implies

\[\sum_{i=1}^{s} f(w_{h-s,i}) + \sum_{i=1}^{s} f(w_{h-s,i-1}w_{h-s,i}) = \sum_{i=1}^{s} f(x_{h-s,i}) + \sum_{i=1}^{s} f(x_{h-s,i-1}x_{h-s,i}).\] (6)

Combining (4),(5) and (6), we got

\[\sum_{i=1}^{s} f(x_{1,i}) + \sum_{i=1}^{s} f(x_{1,i-1}x_{1,i}) = \sum_{i=1}^{s} f(x_{h-s,i}) + \sum_{i=1}^{s} f(x_{h-s,i-1}x_{h-s,i}).\] (7)

Let j ∈ [1, t + 1]. Considering x1,s(t+2−j) and wsj+1,s with s(t + 4) ∈ Dt(x1,s(t+2−j) , wsj+1,s), by Lemma 2.1 (setting m = s) we have

\[\sum_{i=s(t+1-j)+1}^{s(t+2-j)} f(x_{1,i}) + \sum_{i=s(t+1-j)+1}^{s(t+2-j)} f(x_{1,i-1}x_{1,i}) = \sum_{i=1}^{s} f(w_{sj+1,i}) + \sum_{i=1}^{s} f(w_{sj+1,i-1}w_{sj+1,i}).\](8)

Similarly, considering xh−s,sj+1 and wsj+1,s with s(t + 4) ∈ Dt(xh−s,sj+1, wsj+1,s), by Lemma 2.1 (setting m = s) we got

\[\sum_{i=1}^{s} f(w_{sj+1,i}) + \sum_{i=1}^{s} f(w_{sj+1,i-1}w_{sj+1,i}) = \sum_{i=sj+1}^{s(j+1)} f(x_{h-s,i}) + \sum_{i=sj+1}^{s(j+1)} f(x_{h-s,i-1}x_{h-s,i}).\](9)

Combining (8) and (9) for every j yields

\[\sum_{i=s(t+1-j)+1}^{s(t+2-j)} f(x_{1,i}) + \sum_{i=s(t+1-j)+1}^{s(t+2-j)} f(x_{1,i-1}x_{1,i}) = \sum_{i=sj+1}^{s(j+1)} f(x_{h-s,i}) + \sum_{i=sj+1}^{s(j+1)} f(x_{h-s,i-1}x_{h-s,i}).\] (10)

Finally, consider two paths of length h with the consecutive vertices x1,h−s−1, ..., x1,1, v1, w1,1, ..., w1,s and xh−s,h−s−1, ..., xh−s,1, vh−s, wh−s,1, ..., wh−s,s. Since G is Ph-magic, we have

\[\sum_{i=0}^{h-s} f(x_{1,i}) + \sum_{i=1}^{h-s} f(x_{1,i-1}x_{1,i}) + \sum_{i=1}^{s} f(w_{1,i}) + \sum_{i=1}^{s} f(w_{1,i-1}w_{1,i})\] (11)

\[= \sum_{i=0}^{h-s} f(x_{h-s,i}) + \sum_{i=1}^{h-s} f(x_{h-s,i-1}x_{h-s,i}) + \sum_{i=1}^{s} f(w_{h-s,i}) + \sum_{i=1}^{s} f(w_{h-s,i-1}w_{h-s,i}).\](12)

Applying (10) for every j in (11), proceeded by (5) and (7), we have

\[f(x_{1,0}) = f(x_{h-s,0})\]

which is a contradiction of f being a Ph-magic labeling. Therefore, G ∈ F(Ph).

Another class of graphs belonging to F(Ph) are bandana graphs. Here, we define bandana graphs G = Bd(p, q, r, n) as follows

\[V(G) = \{v_i \mid i \in [1, 2q + 1]\} \cup \{x_{b,j}, w_{b,l} \mid b \in \{1, 2q + 1\}, j \in [1, r], l \in [1, p]\}\]\[\cup \{y_k \mid k \in [1, n]\},\]

\[E(G) = \{v_i v_{i+1} \mid i \in [1, 2q]\} \cup \{v_b x_{b,1}, x_{b,j} x_{b,j+1} \mid b \in \{1, 2q+1\}, j \in [1, r-1]\} \cup \{v_b w_{b,1}, w_{b,l} w_{b,l+1} \mid b \in \{1, 2q+1\}, l \in [1, p-1]\} \cup \{v_{q+1} y_1, y_k y_{k+1} \mid k \in [1, n-1]\}.\]

An example of bandana graph is illustrated in Figure 2. The proceeding theorem are some bandana graphs which belongs to F(Ph).

Figure 2. Bandana Bd(1, 1, 3, 2).

Theorem 2.3. Let h, s, t be positive integers. For every pair s, t being a solution of h = 4s + t, then

\[Bd(2s-1, s, 2s+t, 3s-1) \in \mathcal{F}(P_h)\]

Proof. Let h be fixed. Suppose G ∼= Bd(2s − 1, s, 2s + t, 3s − 1) is Ph-magic with a magic labeling f. In this proof, define x1,⁰ = v¹ = w1,⁰ and x2q+1,⁰ = v2q+1 = w2q+1,0. First, consider x1,2s+^t , v1, w1,2s−1, v2s. We can see that 2s − 1 ∈ Dt(v1, w1,2s−1), 2s − 1 ∈ Dt(v1, v2s) and (2s + t) + (2s − 1) = 4s + t − 1 ∈ Dt(x1,2s+^t , w1,2s−1). Therefore, using Lemma 2.2 yields

\[\sum_{i=2}^{2s} f(v_i) + \sum_{i=2}^{2s} f(v_{i-1}v_i) = \sum_{i=1}^{2s-1} f(w_{1,i}) + \sum_{i=1}^{2s-1} f(w_{1,i-1}w_{1,i}).\] (13)

Then, considering w1,2s−¹ and x2q+1,2s+t−¹ with 6s+t−2 ∈ Dt(w1,2s−1, x2q+1,2s+t−1), by Lemma 2.1 (and setting m = 2s − 1) we have

\[\sum_{i=1}^{2s-1} f(w_{1,i}) + \sum_{i=1}^{2s-1} f(w_{1,i-1}w_{1,i}) = \sum_{i=t+1}^{2s+t-1} f(x_{2q+1,i}) + \sum_{i=t+1}^{2s+t-1} f(x_{2q+1,i-1}x_{2q+1,i}).\] (14)

Next, consider x2q+1,2s+t−¹ and y3s−1. Since 6s + t − 2 ∈ Dt(x2q+1,2s+t−1, y3s−1), by Lemma 2.1 (and setting m = 2s − 1) we got

\[\sum_{i=t+1}^{2s+t-1} f(x_{2q+1,i}) + \sum_{i=t+1}^{2s+t-1} f(x_{2q+1,i-1}x_{2q+1,i}) = \sum_{i=s+1}^{3s-1} f(y_i) + \sum_{i=s+1}^{3s-1} f(y_{i-1}y_i).\] (15)

Similarly, considering y3s−¹ and x1,2s+t−¹ with 6s + t − 2 ∈ Dt(y3s−1, x1,2s+t−1), by Lemma 2.1 (and setting m = 2s − 1) we have

\[\sum_{i=s+1}^{3s-1} f(y_i) + \sum_{i=s+1}^{3s-1} f(y_{i-1}y_i) = \sum_{i=t+1}^{2s+t-1} f(x_{1,i}) + \sum_{i=t+1}^{2s+t-1} f(x_{1,i-1}x_{1,i}).\] (16)

Again, consider x1,2s−t+1 and w2q+1,2s−¹ with 6s + t − 2 ∈ Dt(x1,2s−t+1, w2q+1,2s−1), by Lemma 2.1 (setting m = 2s − 1) we got

\[\sum_{i=t+1}^{2s+t-1} f(x_{1,i}) + \sum_{i=t+1}^{2s+t-1} f(x_{1,i-1}x_{1,i}) = \sum_{i=1}^{2s-1} f(w_{2q+1,i}) + \sum_{i=1}^{2s-1} f(w_{2q+1,i-1}w_{2q+1,i}).\] (17)

Finally, consider x2q+1,2s+^t , v2q+1, w2q+1,2s−1, v2. Notice that 2s − 1 ∈ Dt(v2q+1, w2q+1,2s−1), 2s − 1 ∈ Dt(v2q+1, v2) and (2s + t) + (2s−1) = 4s + t−1 ∈ Dt(x2q+1,2s+^t , w2q+1,2s−1). Hence, using Lemma 2.2 yields

\[\sum_{i=1}^{2s-1} f(w_{2q+1,i}) + \sum_{i=1}^{2s-1} f(w_{2q+1,i-1}w_{2q+1,i}) = \sum_{i=2}^{2s} f(v_i) + \sum_{i=3}^{2s+1} f(v_{i-1}v_i).\] (18)

Solving (13) to (18) we have

\[\sum_{i=2}^{2s} f(v_i) + \sum_{i=2}^{2s} f(v_{i-1}v_i) = \sum_{i=2}^{2s} f(v_i) + \sum_{i=3}^{2s+1} f(v_{i-1}v_i)\]

which implies f(v1v2) = f(v2sv2s+1). This contradiction of injectivity of f implies G ∈ F(Ph).

3. Unicyclic graphs in F(Ph)

A result of [7] which states that (n, 1)-tadpole ∈ F(Pn+1) may be generalized into the following theorem.

Theorem 3.1. Let n ≥ 3, p ≥ 1, and n, p be an integer, and m = n+1 2 .

• a) (n, p)-tadpole ∈ F(Pn+p),
• b) (n, p)-tadpole ∈ F(Pm+p).

Proof. For n ≥ 3, p ≥ 1, let G ∼= (n, p)-tadpole be a graph that has a vertex set

\[V(G) = \{v_i, w_j \mid i \in [1, n], j \in [1, p]\},\\]

and an edge set

\[E(G) = \{w_{j-1}w_j, v_{i-1}v_i \mid i \in [1, p], j \in [1, n]\}\]

with w⁰ = v¹ and v⁰ = vn.

First, we want to prove (n, p)-tadpole ∈ F(Pn+p). Suppose G is a Pn+p-magic graph and f is a Pn+p-magic labeling of G. By taking Pn+^p subgraph of G with consecutive vertices wp, wp−1, ..., w1, v1, v2, ..., vⁿ and wp, wp−1, ..., w1, v1, vn, vn−1, ..., v2, we have

\[\sum_{i=1}^{p} f(w_i) + \sum_{i=1}^{n} f(v_i) + \sum_{i=1}^{p-1} f(w_i w_{i+1}) + f(w_1 v_1) + \sum_{i=1}^{n-1} f(v_i v_{i+1})\] \[= \sum_{i=1}^{p} f(w_i) + \sum_{i=1}^{n} f(v_i) + \sum_{i=1}^{p-1} f(w_i w_{i+1}) + f(w_1 v_1) + \sum_{i=2}^{n-1} f(v_i v_{i+1}) + f(v_1 v_n)\]

this implies f(v1v2) = f(v1vn) which is a contradiction from a fact that f is injective.

Next, we will show G ∼= (n, p)-tadpole ∈ F(Pm+p). Suppose G is a Pm+p-magic graph. Consider w^p and vm+1 with m + p − 1 ∈ Dt(wp, vm+1). Using Lemma 2.1, we have

\[f(w_p) + f(w_{p-1}w_p) = f(v_{m+1}) + f(v_m v_{m+1}).\] (19)

Similarly, considering w^p and v^m with m + p − 1 ∈ Dt(wp, vm), applying Lemma 2.1 yields

\[f(w_p) + f(w_{p-1}w_p) = f(v_{n-m+1}) + f(v_{n-m+1}v_{n-m+2}).\] (20)

Therefore, (19) and (20) yields

\[f(v_{m+1}) + f(v_m v_{m+1}) = f(v_{n-m+1}) + f(v_{n-m+1} v_{n-m+2}).\] (21)

Now, divide the problem into cases based on parity of n.

Case 1. n is even

If n is even, let n = 2i, then m = n+1 2 = 2i+1 2 = i implying

\[n - m = m\].

Plugging this into (21) yields

\[f(v_{m+1}) + f(v_m v_{m+1}) = f(v_{m+1}) + f(v_{m+1} v_{m+2})\]

which implies f(vmvm+1) = f(vm+1vm+2) and this leads to a contradiction.

Case 2. n is odd

If n is odd, let n = 2i + 1, then m = n+1 2 = 2i+2 2 = i + 1 which means

\[n - m + 1 = m.\]

Plugging this into (21) giving us

\[f(v_{m+1}) + f(v_m v_{m+1}) = f(v_m) + f(v_m v_{m+1})\]

implying f(vm+1) = f(vm) and this also leads to a contradiction.

In general, most graphs containing cycles belongs to F(Ph). The proceeding theorem provide some sufficient conditions to determine whether a given graph belongs to F(Ph).

Theorem 3.2. Let h ≥ 3, n ≥ 2 and vⁱ , i ∈ [1, n] denotes leaves in a given graph G. If these conditions are satisfied for graph G:

a) \[h \in Dt(v_i, v_{i+1})\] for every \(i \in [1, n]\),

b) \[2h - 1 \in Dt(v_1, v_n) \text{ or } 2h \in Dt(v_1, v_n),\]

then G ∈ F(Ph).

Proof. Suppose G is Ph-magic and has properties as stated in the theorem. For convience, denote e^v as an edge which is incident to a leaf v. For every i ∈ [1.n], since h ∈ Dt(vⁱ , vi+1) then there exists a vertex sequence vⁱ = x1, x2, ..., xn+1 = vi+1 in the graph. Using Lemma 2.1 (setting m = 1), we have

\[f(x_1) + f(x_1 x_2) = f(x_{n+1}) + f(x_n x_{n+1})\]
\[f(v_i) + f(e_{v_i}) = f(v_{i+1}) + f(e_{v_{i+1}})\]

for all i. Consequently, iterating i from 1 to n − 1 yields

\[f(v_1) + f(e_{v_1}) = f(v_n) + f(e_{v_n}). (22)\]

Let r ∈ {2h − 1, 2h} such that r ∈ Dt(v1, vn). Then, there exists a vertex sequence v¹ = y1, y2, ..., yr+1 = vn. Take the subsequence y1, y2, ..., yh+1 and apply Lemma 2.1 (setting m = 1). We have

\[f(y_1) + f(y_1 y_2) = f(y_{h+1}) + f(y_h y_{h+1}).\] (23)

Similarly, taking the subsequence yr−h+1, yr−h+2, ..., yr+1 and applying Lemma 2.1 (setting m = 1 yields

\[f(y_{r-h+1}) + f(y_{r-h+1}y_{r-h+2}) = f(y_{r+1}) + f(y_ry_{r+1}).\] (24)

From (22), (23) and (24), we have

\[f(y_{h+1}) + f(y_h y_{h+1}) = f(y_1) + f(y_1 y_2)\] \[= f(v_1) + f(e_{v_1})\] \[= f(v_n) + f(e_{v_n})\] \[= f(y_{r+1}) + f(y_r y_{r+1})\] \[= f(y_{r-h+1}) + f(y_{r-h+1} y_{r-h+2}).\]

If r = 2h − 1, then we got

\[f(y_{h+1}) = f(y_h)\]

which will contradicts the injectivity of f. Similarly, if r = 2h we have

\[f(y_h y_{h+1}) = f(y_{r-h+1} y_{r-h+2})\]

which also contradicts the injectivity of f. We conclude that G ∈ F(Ph).

In Figure 3, we give an example of a graph satisfying conditions in Theorem 3.2.

Figure 3. A graph G satisfying condition in Theorem 3.2 for h = 5. Hence G ∈ F(P5).

4. Uniqueness of minimal tree in F(P3)

Let G be H-magic with its H-magic labeling f. Recall that K2-supermagic graphs is also called edge-supermagic graphs. Enomoto et al. [2] suggests that there exists a supermagic labeling for every given trees.

Conjecture 1. [2] All trees are edge-supermagic.

The implication of this conjecture is written as follows.

Remark 4.1. If Conjecture 1 is true, then there does not exist trees in F(K2).

Therefore, we want to do similar approach for trying to find trees in F(P3). According to Theorem 1.3, H¹ ∈ F(P3). Our goal is to find whether there exists other trees T ∈ F(P3) which does not contain H¹ while also characterizing trees which are P3-supermagic.

To characterize these trees, we need some theorems that have been established before to be used in our proof. A sufficient condition for trees to have Ph-supermagic has been presented by Maryati et al. [6] with following theorem.

Theorem 4.1. [6] Let G be a tree that admits Ph-covering for some certain integer h ≥ 2. If for every subgraph P^h in G contains a fixed vertex c, then G is Ph-supermagic.

For one class of the tree graph, which is a path, Gutierrez and Llad ´ o [4] showed a sufficient ´ condition for paths Pⁿ to have Ph-magic with a theorem as follows.

Theorem 4.2. [4] Let n ≥ 1 be an integer, then a path Pⁿ is Ph-supermagic for every integer h ∈ [2, n].

Next, we start to characterize trees of order n ∈ [3, 9] which are P3-supermagic. Some labelings are obtained by using the provided theorems.

Theorem 4.3. Every tree of order n ∈ [3, 9] is P3-supermagic if and only if the tree is H1-free.

Proof. The forward direction is just a result from Theorem 1.3 by taking n to be small. To prove the backward direction, we enumerate all trees of order n ∈ [3, 9] which is H1-free is P3-supermagic. All graphs which satisfies the condition is shown to be P3-supermagic by Figure 4. Hence, the theorem holds.

Considering the theorems and results for P3-(super)magic labeling in these trees, we establish a conjecture and its implication as a closure in this section.

Conjecture 2. Every H1-free tree is P3-(super)magic.

Remark 4.2. If Conjecture 2 is true, then T ∈ F(P3) implies H¹ ⊆ T.

5. Concluding Remarks

For future investigation, there are some problems which we found to be interesting.

Problem 1. Can Remark 4.2 be shown without using Conjecture 2?

Problem 2. What are forbidden subgraphs in F(H) for other kind of H?

Acknowledgement

The authors are pleased to give the gratitude for Lulu Tasya Ismaya, Andre Febriantz, and Mada Fatimah for their help in determining the supermagic labeling of trees in small orders. In addition, the authors are also pleased to thank Lisa Damayanti Ningrum for her help in creating the figures.

References

• [1] Darmaji, S. Wahyudi, Rinurwati, and S.W. Saputro, On the construction of super edge-magic total graphs, Electron. J. Graph Theory Appl. 10(1) (2022) 301–309.
• [2] H. Enomoto, A. Llado, T. Nakamigawa, and G. Ringel, Super edge magic graphs, SUT Journal of Mathematics 34(2) (1998) 105–109.
• [3] J.A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin. 14 (2021) #DS6.
• [4] A. Gutierrez and A. Llad ´ o, Magic covering, ´ J. Combin. Math. Combin. Comput. 55 (2005) 43–56.
• [5] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, The consecutively super edge-magic deficiency of graphs and related concepts, Electron. J. Graph Theory Appl. 8(1) (2020) 71– 92.
• [6] T.K. Maryati, E.T. Baskoro, and A.N.M. Salman, Ph-supermagic labelings of some trees, J. Combin. Math. Combin. Comput. 65 (2008) 197–204.
• [7] T.K. Maryati, E.T. Baskoro, A.N.M. Salman, and Irawati, On the path-(super)magicness of a cycle with some pendants, Util. Math. 96 (2015) 319–330.
• [8] Y.F. Ashari, A.N.M. Salman, and R. Simanjuntak, On forbidden subgraphs of (K2, H)-sim- (super)magic graphs, Symmetry 13(8) (2021) 1346.
• [9] S. P. Subbiah and J. Pandimadevi, H-E-Super magic decomposition of graphs, Electron. J. Graph Theory Appl. 2(2) (2014) 115–128.

Figure 4. P3-supermagic trees.