INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS.
VOL.
NO.
NOVEMBER 2023
Further Results on Ph-supermagic Trees Tita Khalis Maryati.
Otong Suhyanto, and Fawwaz Fakhrurrozi Hadiputra AbstractAiLet G be a simple, finite, and undirected graph.
An H-supermagic labeling is a bijective map f : V (G) O E(G) Ie .
, 2.
A A A , |V (G)| |E(G)|} in which f (V ) = .
, 2.
A A A , |VP (G)|} and there P exists an integer m such that w(H A ) = vOOV (H A ) f .
eOOE(H A ) f .
= m, for every subgraph H A O = H in G.
In this paper, we determine some classes of trees which have Ph -supermagic labeling.
Index TermsAiMagic labeling, subgraph covering, trees.
I NTRODUCTION
ET G be a simple, finite, and undirected graph.
Let two isomorphic graphs G and GA are denoted by G O = GA .
A graph G is called a tree if it does not contain any cycles.
An amalgamation of a collection of graphs {Gi } is obtained by picking a vertex to be a terminal in each of Gi , and identifying the graphs by their terminals .
We use the notation Amal{(Gi ), .
for an amalgamation which is obtained from identifying all c from each Gi .
For convenience, let .
, .
= .
| i OO N, a O i O .
Let H be a subgraph of G.
If the graph G has a property that each edges of G belongs to at least one subgraph isomorphic to H in G, we say G admits H-covering.
bijection f : V (G) O E(G) Ie .
, |V (G) E(G)|] is called H-magicPlabeling if there P exists an integer m such that w(H A ) = .
vOOV (H A ) eOOE(H A ) f .
= m, for A O every subgraph H = H of G.
If for every vertex v OO V , f .
OO .
, |V (G)|], then f may also be called H-supermagic.
The problem is to determine whether a certain graph admits H-magic or H-supermagic labeling.
Some known results are found for the subgraph H is isomorphic to either a star K1,n , a cycle Cn , and a path Pn .
GutieArrez and LladoA .
have found that K1,n is K1,h -supermagic if h OO .
, .
and Kn,n is K1,n -magic.
Roswitha and Baskoro .
have determined some double stars, caterpillars, fire crackers, and banana trees to be K1,h -magic for some h.
Moreover, some known graphs which are Ch -magic .
r supermagi.
for some h are found which include wheels, windmills .
, fans, books, ladders .
, and jahangirs .
Furthermore, some results of Ph -magic .
r supermagi.
graphs are also determined.
GutieArrez and LladoA .
found that paths are Ph -supermagic as follows.
Theorem 1: Let n Ou 3 be an integer.
The path Pn is Ph supermagic for any h OO .
, .
Next, let h Ou 3 be an integer.
We define grass graph to be the class graph of trees that admits Ph -covering such that all Maryati and O.
Suhyanto are with Department of Mathematics Education.
UIN Syarif Hidayatullah Jakarta.
Indonesia e-mail:
khalis@uinjkt.
id, otong.
suhyanto@uinjkt.
Hadiputra is with the Master Program of Mathematics.
Institut Teknologi Bandung.
Indonesia e-mail: fawwazfh@alumni.
Manuscript received December 5, 2022.
accepted August 24, 2023.
subgraphs Ph in the graph contain identical vertex, denoted by Rb.
A center of grass graph is the identical vertex of every subgraph Ph .
We may write an equivalent theorem by .
as follows.
Theorem 2: Let h Ou 2 be an integer.
Any graph belongs to Rb.
is Ph -supermagic.
The definition of Rb.
may be used to find a radius of a tree graph.
A radius of a tree graph r(G) may be defined as r(G) = m Oe 1 where m is the least number h such that the graph admits Ph -covering.
Known results are discussing not only sufficient conditions of Ph -magic graphs but also necessary conditions of Ph -magic One of the results is determined by Maryati et al.
stating that Ph -magic graphs cannot contain a subgraph Hn constructed as follows.
Let n Ou 1 be an integer.
Obtain two disjoint odd paths P2n 1 and add one more edge such that the center of those two graphs are adjacent.
Theorem 3: Let n be a positive integer and h OO .
, .
If G is a Ph 2 -magic graph, then G is Hn -free.
Some other Ph -magic .
r supermagi.
graphs are shackles and amalgamations .
, disjoint union of graphs and amalgamations .
, and cycles with some pendants .
Variants for this problem can be seen in .
, .
and for more information of H-magic .
r supermagi.
labeling, please consult to .
In this paper, we would like to investigate more about Ph supermagic tree graphs.
II.
M AIN R ESULTS
Denote ecv to be an edge which belongs to a path from v to c and incident to v.
We start this section by introducing an useful lemma.
Lemma 1: Let h Ou 2 be an integer, and G be a Ph -magic tree with a magic labeling f where t = |V (G)|.
If there exists a subgraph H which belongs to Rb.
with c as a center, such that every pair vi OO H and its incident edge ecvi satisfy f .
i ) f .
cvi ) = 2t 1 then for arbitrary H A which belongs to Rb.
with a center cA .
GA O = Amal{(G.
H A ), cA } is Ph -magic.
Also, if G is Ph -supermagic, then GA is Ph -supermagic.
Proof: Denote n = |V (H A )| Oe 1, or equivalent of total vertices in H A without its center.
Let f A be a labeling of GA .
Then, for every v OO V (G) and e OO E(G), label as follows f A .
= f .
, f A .
= f .
Take all the unused labels .
1, t 2, .
, t 2.
and create a partition into 2-sets, sets consists of two elements, such that the sum of the elements of each 2-set is 2t 2n 1.
Then, use all these 2-sets to label all .
i , ecvi } in any order so that f A .
i ) f A .
cvi ) = 2t 2n 1.
with f A .
i ) < f A .
cvi ).
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS.
VOL.
NO.
NOVEMBER 2023
By evaluating, for every subgraph Ph we got w(Ph ) = .
Oe .
t 2n .
f A .
This lemma enable us to identify the center of any Rb.
to a terminal vertex of Ph -magic graph in order to produce other Ph -magic .
r supermagi.
The terminal vertex chosen for this study is mostly a pendant.
Theorem 4: Let h Ou 3 be an integer and let H belongs to Rb.
The graph G O = Amal{(H.
Ph 1 .
Ph 1 ), .
with c is a center of H and a pendant of each Ph 1 is Ph -supermagic.
Proof: Denote V (G) = V (H) O .
i , vi | i OO .
, h .
} with u1 = v1 = c and E(G) = E(H) O .
i ui 1 , vi vi 1 | i OO .
, .
Let t = |V (G)|.
Define a labeling f as follows f .
2 ) = 5, f .
u2 ) = 2t Oe 4, f .
h 1 ) = 1, f .
h uh 1 ) = 2t Oe 1, f .
2 ) = 6, f .
v2 ) = 2t Oe 5, f .
h 1 ) = 2, f .
h vh 1 ) = 2t Oe 3, f .
= 4.
Compile the unused labels .
O .
, .
, .
O .
1, .
, 2t Oe .
O .
t Oe .
and create a partition of 2-sets such that the sum of the elements of each 2-sets is 2t 1.
Then, use all these 2-sets to label all unlabeled pairs .
i , ecvi }, .
i , ecui } and .
, ecq } for q OO H in any order such that f .
i ) f .
cvi ) = f .
i ) f .
cui ) = f .
cq ) = 2t 1.
with f .
i ) < f .
cvi ), f .
i ) < f .
cui ), and f .
< f .
cq ).
Lemma 1.
G is Ph -supermagic.
An example of a tree for Theorem 4 can be seen in Figure .
i , ecui }, .
i , ecvi }, .
i , ecxi } and .
, ecq } for q OO H in any order such that f .
i ) f .
cvi ) = f .
i ) f .
cui ) =f .
i ) f .
cxi ) = f .
cq ) = 2t 1.
with f .
i ) < f .
cvi ), f .
i ) < f .
cui ), f .
i ) < f .
cxi ) and f .
< f .
cq ).
By Lemma 1.
G is Ph -supermagic.
Theorem 6: Let h Ou 3 be an integer and let H belongs to Rb.
The graph G O = Amal{(H.
Ph 1 .
Ph 2 ), .
with c is a center of H and a pendant both of Ph 1 and Ph 2 is Ph -supermagic.
Proof: Denote V (G) = V (H) O .
i , vi | i OO .
, h .
} O .
h 2 } with u1 = v1 = c and E(G) = E(H) O .
i ui 1 , vi vi 1 | i OO .
, .
} O .
h 1 vh 2 }.
Let t = |V (G)|.
Define a labeling f as follows f .
2 ) = 6, f .
u2 ) = 2t Oe 5, f .
h 1 ) = 1, f .
h uh 1 ) = 2t Oe 2, f .
2 ) = 8, f .
v2 ) = 2t Oe 7, f .
3 ) = 5, f .
2 v3 ) = 2t Oe 4, f .
h 1 ) = 3, f .
h vh 1 ) = 2t Oe 6, f .
h 2 ) = 7, f .
h 1 vh 2 ) = 2t Oe 3, f .
= 4.
Compile the unused labels and create a partition of 2sets such that the sum of the elements of each 2-sets is 2t 1.
Then, use all these 2-sets to label all unlabeled pairs .
i , ecvi }, .
i , ecui } and .
, ecq } for q OO H in any order such f .
i ) f .
cvi ) = f .
i ) f .
cui ) = f .
cq ) = 2t 1.
Fig.
A P5 -supermagic tree.
Theorem 5: Let h Ou 3 be an integer and let H belongs to Rb.
The graph G O = Amal{(H.
Ph 1 .
Ph 1 .
Ph 1 ), .
with c is a center of H and a pendant of each Ph 1 is Ph supermagic.
Proof: Denote V (G) = V (H) O .
i , vi , xi | i OO .
, h .
} with u1 = v1 = x1 = c and E(G) = E(H) O .
i ui 1 , vi vi 1 , xi xi 1 | i OO .
, .
Let t = |V (G)|.
Define a labeling f as follows f .
2 ) = 2, f .
u2 ) = 2t Oe 1, f .
h 1 ) = 7, f .
h uh 1 ) = 2t Oe 6, f .
2 ) = 4, f .
v2 ) = 2t Oe 3, f .
h 1 ) = 6, f .
h vh 1 ) = 2t Oe 5, f .
2 ) = 5, f .
x2 ) = 2t Oe 4, f .
h 1 ) = 1, f .
h xh 1 ) = 2t Oe 2, f .
= 3.
Compile the unused labels and create a partition of 2sets such that the sum of the elements of each 2-sets is 2t 1.
Then, use all these 2-sets to label all unlabeled pairs with f .
i ) < f .
cvi ), f .
i ) < f .
cui ), and f .
< f .
cq ).
Lemma 1.
G is Ph -supermagic.
Before we continue to the next theorem, we need define to define Pn .
Let y be one of a vertices in a path Ph which is adjacent to a pendant.
For n Ou 4, a graph Pn is obtained from a path Pn which the vertex y is attached with one more A pendant z of Pn is called a furthest pendant if it is not adjacent to y.
Theorem 7: Let h Ou 3 be an integer and let H of order at least two belongs to Rb.
The graph G O Amal{(H.
Pn .
Pn ), .
with c is a center of H, and a .
pendant of both Ph and Ph is Ph -supermagic.
Proof: Since the order of H is at least two, there exists a subgraph K2 in H such that V (H) = V (H A ) O .
and E(H) = E(H A ) O .
for some other H A which belongs to Rb.
Denote V (G) = V (H)O.
i , vi | i OO .
, h .
}O.
with u1 = v1 = c and E(G) = E(H) O .
i ui 1 , vi vi 1 | i OO .
, .
} O .
h u h }.
Let t = |V (G)| and r = |V (H)| Oe 2.
Define a labeling f as follows f .
i ) = h Oe i 2, i OO .
, .
, f .
i ui 1 ) = 2t Oe h i, i OO .
, h Oe .
, f .
h 1 ) = h 2, f .
h uh 1 ) = 2t Oe h, f .
h ) = h 3, f .
h u h ) = 2t Oe h Oe 1, f .
2 ) = t Oe r, f .
v2 ) = t r 1.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS.
VOL.
NO.
NOVEMBER 2023
h 1 ) = 1, f .
h vh 1 ) = t h r 1.
Compile the unused labels and create a partition of 2-sets such that the sum of the elements of each 2-sets is 2t 1.
Then, use all these 2-sets to label all unlabeled pairs .
i , ecvi }, .
i , ecui }, and .
, ecq } for q OO H in any order such that Create a partition for A and B into 2-sets such that the sum of the elements of each 2-set is 2.
1 t2 Oe .
for A and 2.
1 t2 ) Oe 1 for B.
Construct a f labeling as follows f .
= t1 , f .
i ) f .
cvi ) = f .
i ) f .
cui ) = f .
cq ) = 2t 1 f .
1 ) = t1 1, with f .
i ) < f .
cvi ), f .
i ) < f .
cui ), and f .
< f .
cq ).
Lemma 1.
G is Ph -supermagic.
An example of a tree in Theorem 7 is illustrated in Figure f .
2 ) = t1 Oe 1, f .
cp1 ) = t1 2t2 Oe 2, f .
cp2 ) = t1 2t2 Oe 1.
Use all 2-sets from A to label all .
, ecv1 } for v OO H1 in any order so that f .
cv1 ) = 2.
1 t2 Oe .
with f .
< f .
cv1 ).
Again, use all 2-sets from B to label all .
, ecu2 } for u OO H2 in any order so that Fig.
A P4 -supermagic tree.
Theorem 8: Let h Ou 2 be an integer and let H.
H belongs to Rb.
If GA O = Amal{(H.
Ph ), .
, where c is a center of H and a pendant of Ph , then the amalgamation GO = Amal{(GA .
H A ), cA } where cA is a center of H A and the other pendant of Ph is Ph -supermagic.
Proof: First, we need to prove GA O = Amal{(H.
Ph ), .
is Ph -supermagic with a magic labeling satisfying the condition of the lemma.
Denote V (GA ) = V (H) O .
OO .
, .
} where c = u1 , p = uh and E(GA ) = E(H) O .
i ui 1 .
OO .
, h Oe .
Let t = |V (GA )|.
Label the vertices and edges as follows f .
i ) = t Oe i 1, f .
i ui 1 ) = t i.
Then, take .
, 2, 3, .
, t Oe .
O .
h, t 2, .
, 2t Oe .
, and create a partition of 2-sets such that the sum of the elements of each 2-set is 2t.
Use all these 2-sets to label all .
i , ecvi } in any order so that f .
cu2 ) = 2.
1 t2 ) Oe 1 where f .
< f .
cu2 ).
Therefore, every vertices have smaller labels from every edges.
Furthermore, for every P3 we got f (P3 ) = 4.
1 t2 ) 6.
Case 2: d.
1 , .
= d.
2 , .
Without loss of generality, d.
1 , .
< d.
2 , .
Let A = .
, t1 Oe .
O .
1 2t2 1, 2.
1 t2 ) Oe .
B = .
1 Oe 1, t1 t2 Oe .
O .
1 t2 1, t1 2t2 Oe .
Create a partition for each A and B into 2-sets such that the sum of the elements of each 2-set is 2.
1 t2 Oe .
for A and 2.
1 n2 ) Oe 3 for B.
Construct a f labeling as follows f .
= t1 Oe 2, f .
1 ) = t1 t2 Oe 3, f .
i ) f .
cvi ) = 2t f .
2 ) = t1 t2 Oe 1, where f .
i ) < f .
cvi ).
By evaluating, for every Ph we got w(Ph ) = .
Oe .
We have shown that GA O = Amal{(H.
Ph ), .
is Ph supermagic with a magic labeling f .
It can be seen that there exists a subgraph H O of GA which belongs to Rb.
with uh as a center.
This subgraph and the magic labeling f are satisfying Lemma 1, hence by applying the lemma, we have Amal{(GA .
H A ), cA } with cA = uh is Ph -supermagic.
Furthermore, the next result is applicable for h = 3.
Theorem 9: Let H1 .
H2 be graphs which belongs to Rb.
Then.
Amal{(H1 .
H2 ), .
where p is a pendant of both H and H A is P3 -supermagic.
Proof: Let |V (Hk )| = tk and ck are the centers of Hk for k OO .
, .
The proof is divided into two cases based on d.
i , .
Case 1: d.
1 , .
= d.
2 , .
Let A = .
, t1 Oe .
O .
1 2t2 , 2.
1 t2 ) Oe .
, f .
cp1 ) = t1 2t2 .
B = .
1 2, t1 2t2 Oe .
cp2 ) = t1 2t2 Oe 1 Choose v1 OO H1 other than c1 or p.
Continue labels as follows f .
1 ) = n1 n2 Oe 2, f .
cv11 ) = t1 t2 .
Use all 2-sets from A to label all .
, ecv1 } for v OO H1 , v = v1 in any order so that f .
cv1 ) = 2.
1 t2 Oe .
with f .
< f .
cv1 ).
Again, use all 2-sets from B to label all .
, ecu2 } for u OO H2 in any order so that f .
cu2 ) = 2.
1 t2 ) Oe 3 with f .
< f .
cu2 ).
Therefore, every vertices have smaller labels from every edges.
Furthermore, for every P3 we got f (P3 ) = 5.
1 t2 ) Oe 7.
Hence, the theorem holds.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS.
VOL.
NO.
NOVEMBER 2023
R EFERENCES
Maryati.
Salman.
Baskoro.
Ryan, and M.
Miller.
AuOn h-supermagic labelings for certain shackles and amalgamations of a connected graph,Ay Utilitas Mathematica, vol.
83, p.
333, 2010.
GutieArrez and A.
LladoA.
AuMagic coverings,Ay Journal of combinatorial mathematics and combinatorial computing, vol.
55, p.
43, 2005.
Roswitha and E.
Baskoro.
AuH-magic covering on some classes of graphs,Ay in AIP Conference Proceedings, vol.
1450, no.
American Institute of Physics, 2012, pp.
135Ae138.
LladoA and J.
Moragas.
AuCycle-magic graphs,Ay Discrete Mathematics, 307, no.
23, pp.
2925Ae2933, 2007.
Jeyanthi and P.
Selvagopal.
AuSome c4-super magic graphs,Ay Ars Combinatoria, vol.
111, pp.
129Ae136, 2013.
Roswitha.
Baskoro.
Maryati.
Kurdhi, and I.
Susanti.
AuFurther results on cycle-supermagic labeling,Ay AKCE International Journal of Graphs and Combinatorics, vol.
10, no.
2, pp.
211Ae220, .
Maryati.
Baskoro, and A.
Salman.
AuPu h-supermagic labelings of some trees,Ay Journal of Combinatorial Mathematics and Combinatorial Computing, vol.
65, p.
197, 2008.
Maryati.
Baskoro.
Salman, and Irawati.
AuOn the path-.
magicness of a cycle with some pendants,Ay Utilitas Mathematica, vol.
319Ae330, 2015.
Maryati.
Salman, and E.
Baskoro.
AuSupermagic coverings of the disjoint union of graphs and amalgamations,Ay Discrete Mathematics, 313, no.
4, pp.
397Ae405, 2013.
Saputra.
Narwen, and E.
Effendi.
AuPelabelan total titik ajaib super pada graf c .
, .
,Ay Jurnal Matematika UNAND, vol.
10, no.
54Ae61, 2021.
Inayah.
Musti, and S.
Masyithoh.
AuAnother antimagic decomposition of generalized peterzen graph,Ay InPrime: Indonesian Journal of Pure and Applied Mathematics, vol.
3, no.
2, pp.
92Ae100, .
Gallian.
AuA dynamic survey of graph labeling,Ay Electronic Journal of combinatorics, vol.
1, no.
DynamicSurveys, p.
DS6, 2018.