Abstract: Let Gbe a simple graph with a vertex set V(G)and edge set E(G). Given a vertex labeling fV:
V(G)→ {0,2,4, . . . , 2kv}and an edge labelings fE:E(G)→ {1,2,3, . . . , 2ke}. Define a function fby
f(x) = fV(x)if x∈V(G)and f(x) = fE(x)if x∈E(G). We call fbe the total k-labeling where k=
max{ke, kv}. A total k-labeling fis called an edge irregular reflexive k-labeling of Gif every two distinct edge
xy and x′y′, we have wtf(xy)
=wtf(x′y′)where wtf(uv) = f(u) + f(uv) + f(v)if uv is an edge of G. The
reflexive edge strength of G, denoted by res(G)is the minimum kfor Gwhich has an edge irregular reflexive
k-labeling. In this paper, we give the exact value of res(Cn+e)where Cn+eis a cycle of order nplus one edge
which contains a triangle.
Key-Words: Reflexive edge strength, edge irregular reflexive, total labeling, graph, label, cycle
5HFHLYHG0D\5HYLVHG1RYHPEHU$FFHSWHG'HFHPEHU3XEOLVKHG-DQXDU\
1 Introduction
Throughout this paper we consider finite, simple
and undirected graphs. Notations and terminologies
not defined here are followed from [1].
Alabeling is a one-to-one mapping that carries a
set of graph elements into a set of non negative inte-
gers, called labels. If a domain is the vertex (or edge)
set, the labeling is called a vertex (or edge) labeling,
respectively. If the domain is both vertex and edge
sets, then the labeling is call a total labeling.
Graph labelings were introduced for the first time
by [2] in 1963. The most complete recent survey of
graph labeling can be found in the Survey of Graph
Labeling written by [3]. The topics of graph labelings
have been studied by a lot of mathematicians in area
of graph theory. The applications of graph labelings
are the benefits indicate in some branch of science,
for examples, coding theory, X-ray, circuit design and
communication network design etc, see [4].
The notation of the irregularity strength of graphs
was introduced in 1988. Then the idea of irregularity
strength was extended to irregular total k-labeling by
[5], [6]. Some previous results of vertex or edge irreg-
ular total k-labeling can be found in [7], [8], [9] and
[10]. After that they extend the concept into an edge
irregular reflexive k-labeling, the complete definition
is defined as the following.
Let G= (V, E)be a simple graph. Given a vertex
labeling fV:V(G)→ {0,2,4, . . . , 2kv}and an
edge labeling fE:E(G)→ {1,2,3, . . . , 2ke}.
Define a function fby f(x) = fV(x)if x∈V(G)
and f(x) = fE(x)if x∈E(G). We call fbe the total
k-labeling where k=max{ke, kv}. Let wtf(uv)be
the weight of the edge uv where wtf(uv) = f(u) +
f(uv)+f(v). A total k-labeling fis called an edge ir-
regular reflexive k-labeling of Gif every two distinct
edge xy and x′y′, we have wtf(xy)=wtf(x′y′).
If Ghas an edge irregular reflexive k-labeling then
the minimum number of kis called reflexive edge
strength of G, denoted by res(G).
In 2017, [11] determined the exact value of res(G)
where Gis a wheel, prism, basket, and fan graph.
Then [12] determined the exact value of res(G)
where Gis a cycle, cartesian product of two cycles,
and join graph of the path and cycle with 2K2in 2019.
Some more relevant results are found in [13] and [14].
In [12], the value of reflexive edge strength of a
cycle Cnwas found. We would like to know that if
we add one edge to a cycle, then the value of its re-
flexive edge strength is whether same or not. We use
the notation Cn+efor a graph by adding one edge to
a cycle Cn. In this paper, we will determine the exact
value of res(Cn+e)where Cn+econtains a triangle.
2 Main Result
The following lemma, proved in [15], shows the
lower bound of the reflexive edge strength for any
graphs.
The Reflexive Edge Strength of Cycles Plus One Edge
1UTHOOMPORN MATO, 2*TANAWAT WICHIANPAISARN
1Department of Mathematics, Faculty of Science,
Srinakharinwirot University, Bangkok 10110,
THAILAND
2Department of Mathematics, Faculty of Applied Science,
King Mongkut's University of Technology North Bangkok,
Bangkok 10800,
THAILAND
∗
Corresponding Author
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.4
Uthoomporn Mato, Tanawat Wichianpaisarn
E-ISSN: 2224-2880
37
Volume 23, 2024
Lemma 2.1. For every graph G,
res(G)≥
⌈|E(G)|
3⌉if |E(G)| ≡ 0,1,4,5 (mod 6),
⌈|E(G)|
3⌉+ 1 if |E(G)| ≡ 2,3 (mod 6).
Lemma 2.1 gives us the lower bound for Cn+e
that will be used in the proof of Theorem 2.3. To
investigate the value of reflexive edge strength of the
grpah Cn+efor n≥4, we first consider the graphs
C4+eand C5+eare as follows.
Proposition 2.2. res(C4+e) = res(C5+e) = 3.
Proof. The graphs C4+eand C5+ehave edge
irregular reflexive 3-labelings as follow (Figure 1).
0
0
0
1
2
32
3
2
2
2
2
2
3
3
00
1
0
22
Figure 1: Edge irregular reflexive 3-labelings of
C4+eand C5+e
Thus res(C4+e)≤3and res(C5+e)≤3.
Suppose that there is an edge irregular reflexive 2-
labeling fof C4+e. If there is an induced subgraph
P3of C4+esuch that all its vertices are labeled by
the same number (see Figure 2), then we have three
remaining edges of C4+eincident to vwhere v∈
V(C4+e)\V(P3). Since edges of C4+emust be
labeled by 1 or 2, by pigeonhole principle, there are
two edges which their weight are not different. This
contradicts the assumption.
Figure 2: An induced subgraph P3of C4+e
Assume that there is no an induced subgraph P3
of C4+esuch that all its vertices are labeled by the
same number. Then there are three edges of C4+ethat
their two endpoints are labeled in the same way. Since
edges of C4+emust be labeled by 1 or 2, there are
two edges which their weight are not different. This
contradicts the assumption. Hence res(C4+e)≥3.
For the graph C5+e, we can consider in the same
way of C4+e, and then we have res(C5+e)≥3.
We give the exact value of reflexive edge strength
of the graph Cn+ewhich contains a triangle in the
next theorem.
Theorem 2.3. For positive integer n,n≥4. Let G
be a graph Cn+ewhich contains a triangle. Then
res(G) =
3if n= 4,5,
n+1
3if n≡0,3,4,5 (mod 6)
and n ≥6,
n+1
3+ 1 if n≡1,2 (mod 6).
Proof. By Proposition 2.2, we have res(C4+e) =
res(C5+e) = 3.
Assume n≥6. By Lemma 2.1 and |E(G)|=
n+ 1, we have
res(G)≥
n+1
3if n≡0,3,4,5 (mod 6)
and n ≥6,
n+1
3+ 1 if n≡1,2 (mod 6).
Case 1 :n≡0,1,2,3 (mod 6).
Let Gbe a graph Cn= (x1, x2, ..., xn, x1)add the
edge x⌈n
2⌉x⌈n
2⌉+2. Define the total labeling fof G
by
f(xi) = 2 i+ 1
3−1, i = 1,2, ..., n
2,
f(xn−i+1) = 2i−1
3, i = 1,2, ..., n
2−1,
f(x⌈n
2⌉+1) = 2n
6n≡0,2,3 (mod 6),
2n
6n≡1 (mod 6),
f(xixi+1) = 2i
3−1, i = 1,2, ..., n
2−1,
f(xn−ixn−i+1) = 2i+ 1
3, i = 1,2, ..., n
2−2,
f(xnx1) = 2,
f(x⌈n
2⌉x⌈n
2⌉+1) = 2n
6+ 1 n≡0 (mod 6),
2n
6−1n≡1,2,3 (mod 6),
f(x⌈n
2⌉+1x⌈n
2⌉+2) = 2n
6n≡0,1,3 (mod 6),
2n
6n≡2 (mod 6),
f(x⌈n
2⌉x⌈n
2⌉+2) = 2n+3
6n≡1,3 (mod 6),
2n
6−1n≡0,2 (mod 6).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.4
Uthoomporn Mato, Tanawat Wichianpaisarn
E-ISSN: 2224-2880
38
Volume 23, 2024
Note that max(f[V(G)∪E(G)])
=n+1
3if , n ≡0,3 (mod 6),
n+1
3+ 1 if , n ≡1,2 (mod 6).
For case n≡0 (mod 6), the weights of the edges
in Cn+eunder the labeling fare the following.
For i= 1,2, ..., n
2−1,
wtf(xixi+1) = f(xi) + f(xixi+1) + f(xi+1)
= 2 i+ 1
3−1+ 2 i
3−1+ 2 i+ 2
3−1
= 2 i+ 1
3+i
3+i+ 2
3−5
= 2(i+ 2) −5
= 2i−1.
For i= 1,2, ..., n
2−2,
wtf(xn−ixn−i+1)
=f(xn−i) + f(xn−1xn−i+1) + f(xn−i+1)
= 2i
3+ 2i+ 1
3+ 2i−1
3
= 2 i−1
3+i
3+i+ 1
3
= 2i+ 2.
wtf(xnx1) = f(xn) + f(xnx1) + f(x1) = 2.
wtf(x⌈n
2⌉x⌈n
2⌉+1)
=f(xn
2) + f(xn
2xn
2+1) + f(xn
2+1)
= 2 n
2+ 1
3−1+2n
6+ 1+ 2n
6
= 2 n
6+ 4 n
6+ 1
=n+ 1.
wtf(x⌈n
2⌉+1x⌈n
2⌉+2)
=f(xn
2+1) + f(xn
2+1xn
2+2) + f(xn
2+2)
= 2n
6+ 2n
6+f(xn−(n
2−1)+1)
= 4n
6+ 2n
2−1−1
3
=4n
6+2n
6=n.
wtf(x⌈n
2⌉x⌈n
2⌉+2)
=f(xn
2) + f(xn
2xn
2+2) + f(xn
2+2)
= 2 n
2+ 1
3−1+2n
6−1+f(xn−(n
2−1)+1)
=2n
6+2n
6−1+2n
6
=n−1.
An example of the total labeling fof C12 +eis
shown in Figure 3.
0
0
0
4
44
0
2
22
0
45
3
3
1
1
1
2
2
2
2
22
2
Figure 3: An edge irregular reflexive 5-labeling of
C12 +e
The weights of the edges in case n≡1,2,3
(mod 6) can be considered similarly.
For case n≡1,3 (mod 6), we have that
wtf(xixi+1) = 2i−1for i= 1,2, . . . , n
2−1,
wtf(xn−ixn−i+1) = 2i+2 for i= 1,2, . . . , n
2−2,
wtf(xnx1) = 2,
wtf(x⌈n
2⌉x⌈n
2⌉+1) = n,
wtf(x⌈n
2⌉+1x⌈n
2⌉+2) = n+ 1,
wtf(x⌈n
2⌉x⌈n
2⌉+2) = n−1.
For case n≡2 (mod 6), we have that
wtf(xixi+1) = 2i−1for i= 1,2, . . . , n
2−1,
wtf(xn−ixn−i+1) = 2i+2 for i= 1,2, . . . , n
2−2,
wtf(xnx1) = 2,
wtf(x⌈n
2⌉x⌈n
2⌉+1) = n+ 1,
wtf(x⌈n
2⌉+1x⌈n
2⌉+2) = n,
wtf(x⌈n
2⌉x⌈n
2⌉+2) = n−1.
We have that the weights of edges in Gare distinct
numbers from the set {1,2, ..., n + 1}.
Hence fis an edge irregular reflexive n+1
3-
labeling of Gfor case n≡0,3 (mod 6) and an edge
irregular reflexive n+1
3+ 1-labeling of Gfor
case n≡1,2 (mod 6).
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.4
Uthoomporn Mato, Tanawat Wichianpaisarn
E-ISSN: 2224-2880
39
Volume 23, 2024
Case 2 :n≡4,5 (mod 6).
Let Gbe a graph Cn= (x1, x2, ..., xn, x1)with
adding the edge x⌈n
2⌉+1x⌈n
2⌉+3.
Define the total labeling fof Gby
f(xi) = 2 i+ 1
3−1, i = 1,2, ..., n
2,
f(xn−i+1) = 2i−1
3, i = 1,2, ..., n
2−2,
f(x⌈n
2⌉+1) = f(x⌈n
2⌉+2) = n+ 1
3,
f(xixi+1) = 2i
3−1,
f(xn−ixn−i+1) = 2i+ 1
3,
f(xnx1) = 2,
f(x⌈n
2⌉+1x⌈n
2⌉+3) = n+ 1
3−2.
Note that max(f[V(G)∪E(G)]) = n+1
3.
For case n≡4 (mod 6), the weights of the edges
in Cn+eunder the labeling fare the following.
For i= 1,2, . . . , n
2,
wtf(xixi+1)
=f(xi) + f(xixi+1) + f(xi+1)
=2i+ 1
3−1+2i
3+ 1+2i+ 2
3−1
= 2 i
3+i+ 1
3+i+ 2
3−5
= 2i−1.
For i= 1,2, . . . , n
2−3,
wtf(xn−ixn−i+1)
=f(xn−i) + f(xn−ixn−i+1) + f(xn−i+1)
= 2i
3+ 2i+ 1
3+ 2i−1
3
= 2 i−1
3+i
3+i+ 1
3
= 2i+ 2.
wtf(xnx1) = f(xn) + f(xnx1) + f(x1) = 2.
wtf(x⌈n
2⌉+1x⌈n
2⌉+2)
=f(x⌈n
2⌉+1) + f(x⌈n
2⌉+1x⌈n
2⌉+2) + f(x⌈n
2⌉+2)
= 2 n
2+ 2
3−1+n+ 1
3+n+ 1
3
= 2 n
2+ 2
3−1+n−1
3+n+ 2
3
= 2 n+ 4
6−1+2n+ 1
3
= 2 n+ 2
6+2n+ 1
3
=n+ 1.
wtf(x⌈n
2⌉+1x⌈n
2⌉+3)
=f(x⌈n
2⌉+1) + f(x⌈n
2⌉+1x⌈n
2⌉+3) + f(x⌈n
2⌉+3)
= 2 n+ 4
6−1+n−4
3+ 2n−6
6
=n+ 8
3−2 + n−4
3+n−4
3
=n−2.
wtf(x⌈n
2⌉+2x⌈n
2⌉+3)
=wtf(x⌈n
2⌉+2xn−(⌊n
2⌋−2)+1)
=f(x⌈n
2⌉+2) + f(x⌈n
2⌉+2x⌈n
2⌉+3) + f(xn−(⌊n
2⌋−2)+1)
=n+ 1
3−1 + n+ 1
3+ 2n
2−2−1
3
=2n+ 4
3+ 2n−6
6
=2n+ 4
3+n+ 2
3−2
=n.
For case n≡5 (mod 6), we can compute in the
same way of case n≡4 (mod 6). Then
wtf(xixi+1) = 2i−1for i= 1,2, . . . , n
2,
wtf(xn−ixn−i+1) = 2i+2 for i= 1,2, . . . , n
2−3,
wtf(xnx1) = 2,
wtf(x⌈n
2⌉+1x⌈n
2⌉+2) = n+ 1,
wtf(x⌈n
2⌉+1x⌈n
2⌉+3) = n−3,
wtf(x⌈n
2⌉+2x⌈n
2⌉+3) = n−1.
We have that the weights of edges in Gare distinct
numbers from the set {1,2, ..., n + 1}. Hence fis an
edge irregular reflexive n+1
3-labeling of G.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.4
Uthoomporn Mato, Tanawat Wichianpaisarn
E-ISSN: 2224-2880
40
Volume 23, 2024
3 Conclusion
In this paper, we obtained the exact values of the
reflexive edge strength of Cn+econtaining a triangle
for all n≥4. In general when we added an edge to
a cycle, the graph might not be contained a triangle,
this issue is still an open problem.
Acknowledgments:
The authors are grateful to anonymous referees for
their valuables comments and several suggestions.
References:
[1] D. B. West, Introduction to graph theory,
Prentice Hall, New Jersey, 2001.
[2] J. Sedlac, Problem 27, Theory of Graphs and Its
Applications, Proceedings of the Symposium
Smolenice, 1963, pp.163-167
[3] J. A. Gallian, A dynamic survey of graph
labeling, Electronic Journal of Combinatorics,
Vol.20, 2017, pp.1-432.
[4] G. Chartrand, L. Lesniak and P. Zhang, Graphs
and Digraphs, sixth ed., Taylor and Francis
Group Boca Raton, New York, 2016.
[5] M. Baca, S. Jendrol, M. Miller and J. Ryan,
Total irregular labelings, Discrete Mathematics,
Vol.307, 2007, pp.1378-1388.
[6] M. Baca and Muhammad K. Siddiqui, Total
edge irregularity strength of generalized prism,
Applied Mathematics Computation, Vol.235,
2014, pp.168-173.
[7] A.Ahmad and M. Baca, On vertex irregular total
labelings, Ars Combinatoria, Vol.112, 2013,
pp.129-139.
[8] I. Tarawneh, R. Hasni and A. Ahmad, On the
edge irregularity strength of corona product of
cycle with isolated vertices, AKCE International
Journal of Graphs and Combinatorics. Vol.13,
2016, pp.213-217.
[9] I. Tarawneh and R. Hasnia A.Ahmad, On the
edge irregularity strength of grid graphs, AKCE
International Journal of Graphs and
Combinatorics, 2018, pp.414-418.
[10] I. Tarawneh, A. Ahmad, G.C. Lau, S.M. Lee
and R. Hasni, On the edge irregularity strength
of corona product of graphs with cycle, Discrete
Math. Algorithms Appl., Vol.12, No.6, 2020.
[11] D. Tanna, J. Ryan and A. Semanicova-
Fenovcikova, Reflexive edge irregular labeling
of prisms and wheels, Australasian Journal of
Combinatorics, Vol.69, No.3, 2017, pp.394-401.
[12] M. Baca, M. Irfan and J. Ryan, A. Semanicova-
Fenovcikova and D. Tanna, Note on edge
irregular reflexive labelings of graphs, AKCE
International Journal of Graphs and
Combinatorics, Vol.16, 2019, pp.145-157.
[13] M. Ibrahim, S. Majeed and M. Siddiqui, Edge
irregular reflexive labeling for star, double star
and caterpillar graphs, TWMS Jounal of Applied
and Engineering Mathematics, Vol.10, No.3,
2020, pp.718-726.
[14] J.L.G. Guirao, S. Ahmad, M.K. Siddiqui and
M. Ibrahim, Edge irregular reflexive labeling for
disjoint union of generalized petersen graph,
Mathematics, Vol.6, No.304, 2018, pp.1-10.
[15] J. Ryan, B. Munasunghe and D. Tanna,
Reflexive irregular labelings, preprint.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
Uthoomporn conceived of the presented idea.
Uthoomporn and Tanawat applied the theory to the
research. Tanawat verified the analytical methods.
All authors discussed the results and contributed to
the design and implementation of the research, to
the analysis of the results and to the writing of the
manuscript.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
The first author appreciates the partial support of
the Faculty of Science, Srinakharinwirot University.
Another author would like to acknowledge the partial
support from the Faculty of Applied Science, King
Mongkut’s University of Technology North Bangkok.
Conflicts of Interest
The authors have no conflicts of interest.
Creative Commons Attribution License 4.0
(Attribution 4.0 International , CC BY 4.0)
This article is published under the terms of the Cre-
ative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.4
Uthoomporn Mato, Tanawat Wichianpaisarn
E-ISSN: 2224-2880
41
Volume 23, 2024
