Electronic Journal of Graph Theory and Applications 12 .
, 43Ae54 Forbidden family of Ph-magic graphs Tita Khalis Maryatia .
Fawwaz Fakhrurrozi Hadiputrab .
Salmanb Department of Mathematics Education.
Universitas Islam Negeri Syarif Hidayatullah Jakarta.
Indonesia b Combinatorial Mathematics Research Group.
Faculty of Mathematics and Natural Sciences.
Institut Teknologi Bandung.
Indonesia khalis@uinjkt.
id, fawwazfh@alumni.
id, msalman@math.
Abstract 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) O E(G) Ie .
, .
is a magic total labeling if for every subgraphs H A isomorphic to H, the sum of labels of all vertices and edges in H A is constant.
If there exists such f , we say G is H-magic.
graph F is said to be a forbidden subgraph of H-magic graphs if F OI 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 Ph is a path of order 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 -.
magic Keywords: Magic labeling, covering, paths, trees Mathematics Subject Classification : 05C78, 05C05 DOI: 10.
5614/ejgta.
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 A which is isomorphic to H.
The graph G is called H-magic if G admits H-covering and there exists total labeling P f : V (G) O E(G)PIe .
, |V (G)| |E(G)|] such that there exists positive integer k which w(H A ) = vOOV (H A ) f .
eOOE(H A ) f .
= Received: 2 July 2022.
Revised: 26 November 2023.
Accepted: 10 December 2023.
Forbidden family of Ph -magic graphs Maryati et al.
k, for each subgraph H A O = H of G.
Furthermore, if f also have extra property f (V (G)) = .
, |V (G)|], then G is H-supermagic.
A special case of K2 -supermagic graphs is called edgesupermagic graphs.
Some results concering H-.
magic graphs can be seen in .
, .
, .
For more information about .
magic labeling and its variations, readers may consult to .
A graph F is called a forbidden subgraph of H-magic if F OI 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 .
, .
, .
, .
We adopt these results in our notation.
Theorem 1.
Let h Ou 3 be positive integer.
We have Ch OO F(Ph ).
A .
, .
-tadpole is a graph constructed by identifying an end vertex of Pk with a vertex of Cn .
Maryati et al.
write Cn 1 O = .
, .
-tadpole.
Theorem 1.
Let h Ou 4 be positive integer.
We have {ChOe1 .
Ch 1 } OI F(Ph ).
Moreover.
Maryati et al.
, .
defined Hn graph with a vertex and edge set V (Hn ) = .
1,i , v2,i | i OO .
, 2n .
E(Hn ) = .
1,i v1,i 1 , v2,i v2,i 1 | i OO .
, 2.
} O .
1,n 1 v2,n 1 }.
They determined that this graph is also a forbidden subgraph of Ph .
Theorem 1.
, .
Let h Ou 3 be positive integer.
We have Hh OO 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 H1 which belongs to F(P3 ) of small order in Section 4.
Trees in F (Ph ) We define Dt.
, .
as a set of every length of possible paths formed with endpoints of v, u.
Clearly, d.
, .
OO Dt.
, .
and for u, v vertices in trees we have Dt.
, .
= .
, .
To start, two supplementary lemmas are provided which arose from the implications of graphs being Ph magic.
The first lemma tells us that some parts in every paths having length more than h in a graph will induce constant sums.
UU] be integers.
Let G be a graph that has f as a Ph -magic Lemma 2.
Let n Ou 3, m OO .
UO nOe1 labeling of G.
If there exists u, v OO V (G) with n OO Dt.
, .
, then there exists consecutive vertices x0 , x1 , .
, xm = u and y0 , y1 , .
, ym = v such that f .
i ) f .
iOe1 xi ) = f .
i ) f .
iOe1 yi ).
Forbidden family of Ph -magic graphs Maryati et al.
Proof.
Since n OO Dt.
, .
, then there exists consecutive vertices u = z1 , z2 , z3 , .
, zn 1 = v.
taking weights of two subgraphs from consecutive vertices z1 , z2 , .
, znOem 1 and zm 1 , zm 2 , .
, zn 1 we have nOem 1 f .
i ) nOem 1 f .
iOe1 zi ) = f .
i ) i=m 1 f .
iOe1 zi ), i=m 2 which implies f .
i ) f .
iOe1 zi ) = f .
i ) i=nOem 2 f .
iOe1 zi ).
i=nOem 2 substituting xi = zmOei 1 and yi = znOem 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.
Let n Ou 3, m OO [ n 1 , nOe.
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 there exists m satisfying m OO Dt.
, .
and m OO Dt.
, .
, there exists n satisfying so that m n OO Dt.
1 , .
, then there exists a consecutive vertices x1 , x2 , .
, xn = w, v1 , v2 , .
, vm = y and x1 , x2 , .
, xn = w, u1 , u2 , .
, um = z such that f .
i ) f .
iOe1 vi ) = f .
i ) f .
iOe1 ui ) with xn = v0 = u0 .
Proof.
By taking two subgraph of consecutive vertices x1 , .
, xn , v1 , .
, vm and x1 , .
, xn , u1 , .
, um we got f .
i ) f .
i ) nOe1 nOe1 f .
i xi 1 ) f .
i xi 1 ) f .
i ) f .
i ) f .
iOe1 vi ) f .
iOe1 ui ).
This implies f .
i ) f .
iOe1 vi ) = f .
i ) f .
iOe1 ui ), therefore the lemma holds.
Forbidden family of Ph -magic graphs Maryati et al.
One kind of a graph belonging to F(Ph ) is a new class of graph namely Tiara graphs.
define a Tiara graph G = T in .
, q, .
as follows V (G) = .
i | i OO .
, .
Oe .
} O .
b,j | b OO .
, .
Oe .
, j OO .
, .
} O .
k 1,l | k OO .
, n Oe .
, l OO .
, .
E(G) = .
i vi 1 | i OO .
, .
Oe .
]} O .
b xb,1 , xb,j xb,j 1 | b OO .
, .
Oe .
, j OO .
, r Oe .
} O .
k 1 w.
k 1,1 , w.
k 1,l w.
k 1,l 1 | k OO .
, n Oe .
, l OO .
, p Oe .
An example of T i4 .
, 1, .
is depicted in Figure 1.
Theorem 2.
1 and Theorem 2.
2 deals with tiara graphs which belongs to F(Ph ).
Figure 1.
Tiara T i4 .
, 1, .
Theorem 2.
Let h, s be positive integers with s Ou 2.
For every s being a solution of h.
, the following statements are true.
If h = 2s 1, then T i2 .
, s Oe 1, .
OO F(Ph ).
If h = 2s, then T i2 .
Oe 1, s Oe 1, .
OO F(Ph ).
Proof.
Let h be fixed.
To prove part .
simultaneously we set G O = T i2 .
Oe s Oe 1, s Oe 1, .
Suppose G is Ph -magic with f as a Ph -magic labeling for G.
In this proof, define w1,0 = v1 and ws 1,0 = vs 1 .
Consider x1,s , v1 , vhOes , w1,hOesOe1 .
Notice that h Oe s Oe 1 OO Dt.
1 , vhOes ), h Oe s Oe 1 OO Dt.
1 , w1,hOesOe1 ) and .
Oe s Oe .
s = h Oe 1 OO Dt.
1,s , vhOes ).
Therefore, by Lemma 2 we have hOes f .
i ) hOes f .
iOe1 vi ) = hOesOe1 f .
1,i ) hOesOe1 f .
1,iOe1 w1,i ).
Next, consider w1,hOesOe1 and ws 1,hOesOe1 .
Since 2h Oe s Oe 2 OO Dt.
1,hOesOe1 , ws 1,hOesOe1 ), by Lemma 1 .
etting m = h Oe s Oe .
we have hOesOe1 f .
1,i ) hOesOe1 f .
1,iOe1 w1,i ) = hOesOe1 f .
s 1,i ) hOesOe1 f .
s 1,iOe1 ws 1,i ).
Then, consider xs 1,s , vs 1 v2s 2Oeh , ws 1,hOesOe1 .
Notice that h Oe s OO Dt.
s 1 , v2s 2Oeh ), h Oe s OO Dt.
s 1 , ws 1,hOesOe1 ) and .
Oe .
s = h OO Dt.
s 1,s , vs 1 ).
Therefore, by Lemma 2.
2 we have hOesOe1 f .
s 1,i ) hOesOe1 f .
s 1,iOe1 ws 1,i ) = i=2s 2Oeh f .
i ) f .
iOe1 vi ).
i=2s sOeh 1 Forbidden family of Ph -magic graphs Maryati et al.
From .
, .
, we have hOes f .
i ) hOes f .
iOe1 vi ) = f .
i ) i=2s 2Oeh f .
iOe1 vi ).
i=2s 2Oeh 1 If h = 2s 1, this would imply f .
1 ) = f .
s 1 ).
On the other hand, h = 2s implies f .
1 v2 ) = f .
s vs 1 ).
The contradictions of injectivity of f in both cases are implying T i2 .
OesOe1, sOe1, .
OO F(Ph ).
Theorem 2.
Let h, s, t be positive integers.
For every pair s, t being a solution of h = s.
T i.
, s Oe 1, s.
) OO F(Ph ).
Proof.
Let h be fixed.
Suppose G O = T i.
, s Oe 1, s.
) is Ph -magic with a magic labeling In this proof, define xk,0 = vk = wk,0 for every k OO .
, h Oe .
ote that h Oe s = .
First, consider vhOes , v1 , x1,s , w1,s .
Notice that s OO Dt.
1 , x1,s ), s OO Dt.
1 , w1,s ) and s s.
= s.
OO Dt.
hOes , x1,s ).
Hence, by Lemma 2.
2, we have f .
1,i ) f .
1,iOe1 x1,i ) = f .
1,i ) f .
1,iOe1 w1,i ).
Then, considering w1,s and whOes,s with s.
OO Dt.
1,s , whOes,s ) by Lemma 2.
etting m = .
we have f .
1,i ) f .
1,iOe1 w1,i ) = f .
hOes,i ) f .
hOes,iOe1 whOes,i ).
Next, consider v1 , vhOes , xhOes,s , whOes,s .
We can see that s OO Dt.
hOes , xhOes,s ), s OO Dt.
hOes , whOes,s ) and s s.
= s.
OO Dt.
1 , vhOes,s ).
Therefore, by Lemma 2.
2 implies f .
hOes,i ) f .
hOes,iOe1 whOes,i ) = f .
hOes,i ) f .
hOes,iOe1 xhOes,i ).
Combining .
, we got f .
1,i ) f .
1,iOe1 x1,i ) = f .
hOes,i ) f .
hOes,iOe1 xhOes,i ).
Let j OO .
, t .
Considering x1,s.
2Oe.
and wsj 1,s with s.
OO Dt.
1,s.
2Oe.
, wsj 1,s ), by Lemma 2.
etting m = .
we have s.
2Oe.
i=s.
1Oe.
1 s.
2Oe.
1,i ) f .
1,iOe1 x1,i ) = i=s.
1Oe.
1 f .
sj 1,i ) f .
sj 1,iOe1 wsj 1,i ).
Forbidden family of Ph -magic graphs Maryati et al.
Similarly, considering xhOes,sj 1 and wsj 1,s with s.
OO Dt.
hOes,sj 1 , wsj 1,s ), by Lemma 2.
etting m = .
we got f .
sj 1,i ) s.
sj 1,iOe1 wsj 1,i ) = f .
hOes,i ) f .
hOes,iOe1 xhOes,i ).
i=sj 1 i=sj 1 Combining .
for every j yields s.
2Oe.
2Oe.
1,i ) i=s.
1Oe.
1 f .
1,iOe1 x1,i ) = s.
hOes,i ) i=sj 1 i=s.
1Oe.
1 f .
hOes,iOe1 xhOes,i ).
i=sj 1 Finally, consider two paths of length h with the consecutive vertices x1,hOesOe1 , .
, x1,1 , v1 , w1,1 , .
, w1,s and xhOes,hOesOe1 , .
, xhOes,1 , vhOes , whOes,1 , .
, whOes,s .
Since G is Ph -magic, we have hOes hOes f .
1,i ) hOes f .
1,iOe1 x1,i ) hOes f .
hOes,i ) f .
1,i ) f .
1,iOe1 w1,i ) .
hOes,iOe1 xhOes,i ) f .
hOes,i ) f .
hOes,i=1 whOes,i ).
Applying .
for every j in .
, proceeded by .
, we have f .
1,0 ) = f .
hOes,0 ) which is a contradiction of f being a Ph -magic labeling.
Therefore.
G OO F(Ph ).
Another class of graphs belonging to F(Ph ) are bandana graphs.
Here, we define bandana graphs G = Bd.
, q, r, .
as follows V (G) = .
i | i OO .
, 2q .
} O .
b,j , wb,l | b OO .
, 2q .
, j OO .
, .
, l OO .
, .
} O .
k | k OO .
, .
E(G) = .
i vi 1 | i OO .
, 2.
} O .
b xb,1 , xb,j xb,j 1 | b OO .
, 2q .
, j OO .
, r Oe .
} O .
b wb,1 , wb,l wb,l 1 | b OO .
, 2q .
, l OO .
, p Oe .
} O .
q 1 y1 , yk yk 1 | k OO .
, n Oe .
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, 3, .
Forbidden family of Ph -magic graphs Maryati et al.
Theorem 2.
Let h, s, t be positive integers.
For every pair s, t being a solution of h = 4s t.
Bd.
s Oe 1, s, 2s t, 3s Oe .
OO F(Ph ) Proof.
Let h be fixed.
Suppose G O = Bd.
s Oe 1, s, 2s t, 3s Oe .
is Ph -magic with a magic labeling f .
In this proof, define x1,0 = v1 = w1,0 and x2q 1,0 = v2q 1 = w2q 1,0 .
First, consider x1,2s t , v1 , w1,2sOe1 , v2s .
We can see that 2s Oe 1 OO Dt.
1 , w1,2sOe1 ), 2s Oe 1 OO Dt.
1 , v2s ) and .
s Oe .
= 4s t Oe 1 OO Dt.
1,2s t , w1,2sOe1 ).
Therefore, using Lemma 2.
2 yields f .
i ) f .
iOe1 vi ) = 2sOe1 f .
1,i ) 2sOe1 f .
1,iOe1 w1,i ).
Then, considering w1,2sOe1 and x2q 1,2s tOe1 with 6s t Oe 2 OO Dt.
1,2sOe1 , x2q 1,2s tOe1 ), by Lemma 1 .
nd setting m = 2s Oe .
we have 2sOe1 f .
1,i ) 2sOe1 f .
1,iOe1 w1,i ) = 2s tOe1 2s tOe1 f .
2q 1,i ) i=t 1 f .
2q 1,iOe1 x2q 1,i ).
i=t 1 Next, consider x2q 1,2s tOe1 and y3sOe1 .
Since 6s t Oe 2 OO Dt.
2q 1,2s tOe1 , y3sOe1 ), by Lemma 2.
nd setting m = 2s Oe .
we got 2s tOe1 f .
2q 1,i ) 2s tOe1 i=t 1 f .
2q 1,iOe1 x2q 1,i ) = i=t 1 3sOe1 f .
i ) i=s 1 3sOe1 f .
iOe1 yi ).
i=s 1 Similarly, considering y3sOe1 and x1,2s tOe1 with 6s t Oe 2 OO Dt.
3sOe1 , x1,2s tOe1 ), by Lemma 2.
nd setting m = 2s Oe .
we have 3sOe1 f .
i ) i=s 1 3sOe1 f .
iOe1 yi ) = i=s 1 2s tOe1 f .
1,i ) i=t 1 2s tOe1 f .
1,iOe1 x1,i ).
i=t 1 Again, consider x1,2sOet 1 and w2q 1,2sOe1 with 6s t Oe 2 OO Dt.
1,2sOet 1 , w2q 1,2sOe1 ), by Lemma 1 .
etting m = 2s Oe .
we got 2s tOe1 f .
1,i ) i=t 1 2s tOe1 f .
1,iOe1 x1,i ) = i=t 1 2sOe1 f .
2q 1,i ) 2sOe1 f .
2q 1,iOe1 w2q 1,i ).
Finally, consider x2q 1,2s t , v2q 1 , w2q 1,2sOe1 , v2 .
Notice that 2s Oe 1 OO Dt.
2q 1 , w2q 1,2sOe1 ), 2s Oe 1 OO Dt.
2q 1 , v2 ) and .
s Oe .
= 4s t Oe 1 OO Dt.
2q 1,2s t , w2q 1,2sOe1 ).
Hence, using Lemma 2.
2 yields 2sOe1 f .
2q 1,i ) 2sOe1 f .
2q 1,iOe1 w2q 1,i ) = f .
i ) f .
iOe1 vi ).
Forbidden family of Ph -magic graphs Maryati et al.
Solving .
we have f .
i ) f .
iOe1 vi ) = f .
i ) f .
iOe1 vi ) which implies f .
1 v2 ) = f .
2s v2s 1 ).
This contradiction of injectivity of f implies G OO F(Ph ).
Unicyclic graphs in F (Ph ) A result of .
which states that .
, .
-tadpole OO F(Pn 1 ) may be generalized into the following theorem.
Theorem 3.
Let n Ou 3, p Ou 1, and n, p be an integer, and m = n 1 .
, .
-tadpole OO F(Pn p ), .
, .
-tadpole OO F(Pm p ).
Proof.
For n Ou 3, p Ou 1, let G O = .
, .
-tadpole be a graph that has a vertex set V (G) = .
i , wj | i OO .
, .
, j OO .
, .
}, and an edge set E(G) = .
jOe1 wj , viOe1 vi | i OO .
, .
, j OO .
, .
} with w0 = v1 and v0 = vn .
First, we want to prove .
, .
-tadpole OO 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 , wpOe1 , .
, w1 , v1 , v2 , .
, vn and wp , wpOe1 , .
, w1 , v1 , vn , vnOe1 , .
, v2 , we have f .
i ) f .
i ) pOe1 f .
i wi 1 ) f .
1 v1 ) nOe1 pOe1 nOe1 f .
i ) f .
i ) f .
i wi 1 ) f .
1 v1 ) f .
i vi 1 ) f .
i vi 1 ) f .
1 vn ) this implies f .
1 v2 ) = f .
1 vn ) which is a contradiction from a fact that f is injective.
Next, we will show G O = .
, .
-tadpole OO F(Pm p ).
Suppose G is a Pm p -magic graph.
Consider wp and vm 1 with m p Oe 1 OO Dt.
p , vm 1 ).
Using Lemma 2.
1, we have f .
p ) f .
pOe1 wp ) = f .
m 1 ) f .
m vm 1 ).
Similarly, considering wp and vm with m p Oe 1 OO Dt.
p , vm ), applying Lemma 2.
1 yields f .
p ) f .
pOe1 wp ) = f .
nOem 1 ) f .
nOem 1 vnOem 2 ).
Forbidden family of Ph -magic graphs Maryati et al.
Therefore, .
yields f .
m 1 ) f .
m vm 1 ) = f .
nOem 1 ) f .
nOem 1 vnOem 2 ).
Now, divide the problem into cases based on parity of n.
Case 1.
n is even 2i 1 = 2 = i implying If n is even, let n = 2i, then m = n 1 n Oe m = m.
Plugging this into .
yields f .
m 1 ) f .
m vm 1 ) = f .
m 1 ) f .
m 1 vm 2 ) which implies f .
m vm 1 ) = f .
m 1 vm 2 ) and this leads to a contradiction.
Case 2.
n is odd 2i 2 If n is odd, let n = 2i 1, then m = n 1 = 2 = i 1 which means n Oe m 1 = m.
Plugging this into .
giving us f .
m 1 ) f .
m vm 1 ) = f .
m ) f .
m vm 1 ) implying f .
m 1 ) = f .
m ) 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.
Let h Ou 3, n Ou 2 and vi , i OO .
, .
denotes leaves in a given graph G.
If these conditions are satisfied for graph G:
h OO Dt.
i , vi 1 ) for every i OO .
, .
, .
2h Oe 1 OO Dt.
1 , vn ) or 2h OO Dt.
1 , vn ), then G OO F(Ph ).
Proof.
Suppose G is Ph -magic and has properties as stated in the theorem.
For convience, denote ev as an edge which is incident to a leaf v.
For every i OO .
, since h OO Dt.
i , vi 1 ) then there exists a vertex sequence vi = x1 , x2 , .
, xn 1 = vi 1 in the graph.
Using Lemma 2.
etting m = .
, we have f .
1 ) f .
1 x2 ) = f .
n 1 ) f .
n xn 1 ) f .
i ) f .
vi ) = f .
i 1 ) f .
vi 1 ) Forbidden family of Ph -magic graphs Maryati et al.
for all i.
Consequently, iterating i from 1 to n Oe 1 yields f .
1 ) f .
v1 ) = f .
n ) f .
vn ).
Let r OO .
h Oe 1, 2.
such that r OO Dt.
1 , vn ).
Then, there exists a vertex sequence v1 = y1 , y2 , .
, yr 1 = vn .
Take the subsequence y1 , y2 , .
, yh 1 and apply Lemma 2.
etting m = .
We have f .
1 ) f .
1 y2 ) = f .
h 1 ) f .
h yh 1 ).
Similarly, taking the subsequence yrOeh 1 , yrOeh 2 , .
, yr 1 and applying Lemma 2.
etting m = 1 f .
rOeh 1 ) f .
rOeh 1 yrOeh 2 ) = f .
r 1 ) f .
r yr 1 ).
From .
, .
, we have f .
h 1 ) f .
h yh 1 ) = f .
1 ) f .
1 y2 ) = f .
1 ) f .
v1 ) = f .
n ) f .
vn ) = f .
r 1 ) f .
r yr 1 ) = f .
rOeh 1 ) f .
rOeh 1 yrOeh 2 ).
If r = 2h Oe 1, then we got f .
h 1 ) = f .
h ) which will contradicts the injectivity of f .
Similarly, if r = 2h we have f .
h yh 1 ) = f .
rOeh 1 yrOeh 2 ) which also contradicts the injectivity of f .
We conclude that G OO F(Ph ).
In Figure 3, we give an example of a graph satisfying conditions in Theorem 3.
Figure 3.
A graph G satisfying condition in Theorem 3.
2 for h = 5.
Hence G OO F(P5 ).
Forbidden family of Ph -magic graphs Maryati et al.
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.
suggests that there exists a supermagic labeling for every given trees.
Conjecture 1.
All trees are edge-supermagic.
The implication of this conjecture is written as follows.
Remark 4.
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.
H1 OO F(P3 ).
Our goal is to find whether there exists other trees T OO F(P3 ) which does not contain H1 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 .
with following theorem.
Theorem 4.
Let G be a tree that admits Ph -covering for some certain integer h Ou 2.
If for every subgraph Ph in G contains a fixed vertex c, then G is Ph -supermagic.
For one class of the tree graph, which is a path.
GutieArrez and LladoA .
showed a sufficient condition for paths Pn to have Ph -magic with a theorem as follows.
Theorem 4.
Let n Ou 1 be an integer, then a path Pn is Ph -supermagic for every integer h OO .
, .
Next, we start to characterize trees of order n OO .
, .
which are P3 -supermagic.
Some labelings are obtained by using the provided theorems.
Theorem 4.
Every tree of order n OO .
, .
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 OO .
, .
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 -.
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 -.
Remark 4.
If Conjecture 2 is true, then T OO F(P3 ) implies H1 OI T .
Forbidden family of Ph -magic graphs Maryati et al.
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.
addition, the authors are also pleased to thank Lisa Damayanti Ningrum for her help in creating the figures.
References