# On the Construction of the Reflexive Vertexk-Labeling of Any Graph with Pendant Vertex

Authors: I. H. Agustin; M. I. Utoyo; Dafik; M. Venkatachalam; Surahmat
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

A totalk-labeling is a function fe from the edge set to first natural number ke and a function fv from the vertex set to non negative even number up to 2kv, where k=maxke,2kv. A vertex irregular reflexivek-labeling of a simple, undirected, and finite graph G is total k-labeling, if for every two different vertices x and x′ of G, wtx≠wtx′, where wtx=fvx+Σxy∈EGfexy. The minimum k for graph G which has a vertex irregular reflexive k-labeling is called the reflexive vertex strength of the graph G, denoted by rvsG. In this paper, we determined the exact value of the reflexive vertex strength of any graph with pendant vertex which is useful to analyse the reflexive vertex strength on sunlet graph, helm graph, subdivided star graph, and broom graph.


---

## Body

## 1. Introduction

We consider a simple and finite graphG=V,E with vertex set VG and edge set EG. We motivate the readers to refer Chartrand et al. [1], for detailed definition of the graph. A topic in graph theory which has grown fast is the labeling of graphs. The concept of graph labeling, firstly, was introduced by Wallis in [2]. He defined a labeling of G is a mapping that carries a set of graph elements into a set of integers called labels. By this definition, we can have a vertex label, edge label, or both of them. Baca et al. [3] introduced the total labeling, and they defined the vertex weight as the sum of all incident edge labels along with the label of the vertices. Many types of labeling have been studied by researchers, namely, graceful labeling, magic labeling, antimagic labeling, irregular labeling, and irregular reflexive labeling.Furthermore, labeling known as a vertex irregular totalk-labeling and total vertex irregularity strength of graph is the minimum k for which the graph has a vertex irregular total k-labeling. The bounds for the total vertex irregularity strength are given in [3]. In [4], Tanna et al. identified the concept of vertex irregular reflexive labeling of graphs. In this paper, we continue to study a vertex irregular reflexive labeling as there are still many open problems. By irregular reflexive labeling, we mean a labeling of graph which the vertex labels are assigned by even numbers from 0,2,…,2k and the edge labels are assigned by 1,2,3,…,k, where k is positive integer. The weight of each vertex, under a total labeling, is determined by summing the incident edge labels and the label of the vertex itself.Ak-labeling assigns numbers 1,2,…,k to the elements of graph. Let k be a natural number, a function f:VG∪EG⟶1,2,3,…,k is called total k-irregular labeling. Hinding et al. [5] defined that a total labeling ϕ:VG∪EG⟶1,2,3,…,k is called vertex irregular total k-labeling of graph G if the vertex weight wtϕx=ϕx+Σxy∈EGϕxy is distinct for every two different vertices, wtϕx≠wtϕy for x,y∈VG,x≠y. The minimum k for which graph G has a vertex irregular total k-labeling is called total vertex irregularity strength, denoted by tvsG.The concept of vertex irregular totalk-labeling extends to a vertex irregular reflexive total k-labeling. The definition of total k-labeling is a function fe from the edge set to the first natural number ke and a function fv from the vertex set to the nonnegative even number up to 2kv, where k=maxke,2kv. A vertex irregular reflexivek-labeling of the graph G is the total k-labeling, for every two different vertices x and x′ of G, wtx≠wtx′, where wtx=fvx+Σxy∈EGfexy. The minimum k for graph G which has a vertex irregular reflexive k-labeling is called the reflexive vertex strength of the graph G, denoted by rvsG.Some results related to vertex irregular reflexive labeling have been studied by several researchers. Tanna et al. [4] have studied the vertex irregular reflexive of prism and wheel graphs, Ahmad and Bac̆a [6] have studied the total vertex irregularity strength for two families of graphs, namely, Jahangir graphs and circulant graphs, and Agustin et al. [7] also study the concept of vertex irregular reflexive labeling of cycle graph and generalized friendship. Another results of irregular labeling can be seen on [8–15]. In this paper, we have found the lower bound of vertex irregular reflexive strength of any graph G and determined the vertex irregular reflexive strength of graphs with pendant vertex. Our results are started by showing one lemma and theorem which describe a general construction of the existence of vertex irregular reflexive k-labeling of graph with pendant vertex.


## 2. Result and Discussion

The following lemma and theorem will be used as a base construction of analysing the reflexive vertex strength of any graph with pendant vertex, namely, sunlet graph, helm graph, subdivided star graph, and broom graph.Lemma 1.
For any graphG of order p, the minimum degree δ, and the maximum degree Δ,(1)rvsG≥p+δ−1Δ+1.Proof. LetG be a graph of order p, the minimum degree δ, and the maximum degree Δ. The total k-labeling which labeling f defined fe:EG⟶1,2,…,ke and fv:VG⟶0,2,…,2kv such that fx=fvx if x∈VG and fx=fex if x∈EG, where k= maxke,2kv. The total k-labeling f is called a vertex irregular reflexive k-labeling of the graph G if every two different vertices x and x′, and it holds wtx≠wtx′, where wtx=fvx+Σxy∈EGfexy. Furthermore, since we require k-minimum for the graph G which has a vertex irregular reflexive labeling, the set of a vertex weight should be consecutive, otherwise it will not give a minimum rvs. Thus, the set of a vertex weight is Wtx=δ,δ+1,δ+2,…,12kv+Δke. Since the minimum k=maxke,2kv is the reflexive vertex strength, the maximum possible vertex weight of graph G is at most k1+Δ. It implies 2kv+Δke≥δ+p−1.1↔k+Δk≥δ+p−1↔k≥δ+p−1/Δ+1. Since rvsG should be integer and we need a sharpest lower bound, it implies(2)rvsG≥δ+p−1Δ+1.It completes the proof.Theorem 1.
LetG be a graph of order n and contains l pendant vertex. If l≥n−l, then(3)rvsG=l2+1,forleven andl2odd,l2,otherwise.Proof.
Given that a graphG of order n is with l pendant vertices. The labeling of graph G is with respect to two components, namely, the pendant vertices and otherwise vertices. Thus, we will split our proof into two cases.Case 1.
LetVl be a set of pendant vertices and the number of Vl is l. A pendant vertex consists of two elements, i.e., a vertex and an edge. The vertex weight on each pendant vertex must be different. Suppose we choose those vertex weights are 1,2,…,l. Those vertex weights are obtained by summing the vertex and edge labels. To prove the above rvsG, let us suppose the maximum vertex weight of l. Let(4)l2=l+12,forlodd,l2,forleven.
Define an injectionf as the labels. Since the weight l is contributed by one vertex and one edge labels, it will give four possibilities.(1)
Ifl+1/2 is odd number, then fv=l+1/2−1 and fe=l+1/2, such that the vertex weight is l+1/2−1+l+1/2=l+1−1=l(2)
Ifl+1/2 is even number, then fv=l+1/2 and fe=l+1/2, such that the vertex weight is l+1/2+l+1/2=l+1(3)
Ifl/2 is odd number, then fv=l/2−1 and fe=l/2, such that the vertex weight is l/2−1+l/2=l−1(4)
Ifl/2 is even number, then fv=l/2 and fe=l/2, such that the vertex weight is l/2+l/2=l
The vertex weight of point1,2, and (4) are, respectively, l and l+1. It will give all weights are different, whereas, point (3) has a vertex weight of l−1. Since the number of pendants is l, we will have at least two vertices which have the same weight. Therefore, for l is even and l/2 is odd, we need to add 1 for the largest vertex or edge labels. Thus, we will have a different weight for every pendant. Thus, the labels of vertex and edge of the pendant are the following.
From Table1, it is easy to see that all vertex weights are different.Table 1
Labeling of vertex and edge on pendant vertices.
viv1v2v3…vkvk+1vk+2vk+3vk+4…vl−1vlfv000…02244…kkfe123…kk−1kk−1k…k−1kwvi123…kk+1k+2k+3k+4…2k−12k(5)k=l2+1,forleven andl2odd,l2,otherwise.Case 2.
The vertex set apart from pendant verticesVG−Vl must have a degree of at least two. The cardinality of VG−Vl is less than or equal to the cardinality of Vl. It implies that the vertex or edge labels of pendant vertices can be re-used on labels of VG−Vl. Thus, the vertex weight of VG−Vl will be different with the vertices of Vl since it has more combination, namely, 2k+1,2k+2,…,n.
Based on Case1 and Case 2, the reflexive vertex strength of graph G is(6)rvsG=l2+1,forleven andl2odd,l2,otherwise.
It concludes the proof.Corollary 1.
LetSnbe a sunlet graph, and for everyn≥3,(7)rvsSn=n2+1,ifneven andn2odd,n2,otherwise.Proof.
Moreover, to determine the label of verticesVSn=ui,vi;1≤i≤n and edge set ESn=uivi,1≤i≤n∪uiui+1,1≤i≤n−1∪u1un, we will use (Algorithm 1)(8)k=n2+1,ifneven andn2odd,n2,otherwise.
It concludes the proof.
For an illustration, see Figure1.Algorithm 1: The vertices’ and edges’ labels.
(1)
Definev∈VG, e∈EG and injecton f for labeling of the graph elements(2)
Assign the labels of vertices and edges of pendantsvi according to Theorem 1.(3)
Observe that the vertex weight on each pendant will be1,2,…,k,k+1,…,n=2k or 1,2,…,k,k+1,…,n=2k−1.(8)
The vertex weights of point (4),(7) arel, but 5, 6 are respectively is l+1 and l−1. Since the number of pendant vertices is l, it will exist two type of vertices which have the same weights. Do the following.(9)
Whenl is even and l/2 is odd, add the label of each vertex or edge by 1.(10)
Apart from pendants, assign the label of verticesui as the label of pendant vertices vi, but the labels of edges uiui+1,1≤i≤n−1 with k, thus the vertex weights are 2k+1,2k+2,…,3k,3k+1,…4k or 2k+1,2k+2,…,3k,3k+1,…4k−1.(11)
Observe, all pendant vertices and otherwise show a different vertex weight.(11)
STOP.Figure 1
The illustration of labeling onS7 and S12.Theorem 2.
LetHnbe a helm graph, and for everyn≥3,(9)rvsHn=n2+1,ifneven andn2odd,n2,otherwise.Proof.
LetHn be a helm graph with vertex set VHn=A,ui,vi;1≤i≤n, VHn=2n+1 and edge set EHn=Aui,uivi,1≤i≤n∪uiui+1,1≤i≤n−1∪u1un,EHn=3n. Helm graph has n pendant vertices and one central vertex of degree n. Since the central vertex has degree of much greater than the other vertices, it must have a different vertex weight than the others. Based on Theorem 1, we have the following lower bound:(10)rvsHn≥n2+1,ifneven andn2odd,n2,otherwise.
Furthermore, we will show the upper bound of vertex irregular reflexivek-labeling by defining the injection f and g in the following:(11)fA=0,fui=fvi,fvi=0,if1≤i≤k,2i−k2,ifk+1≤i≤n,gAui=guiui+1=gu1un=k,guivi=i,if1≤i≤k,k−1,ifk+1≤i≤n,iodd forkevenandieven forkodd,k,ifk+1≤i≤n,ieven forkevenandiodd forkodd,where(12)k=n2+1,ifneven andn2odd,n2,otherwise.
Based on the above injection, the overall vertex weight sets are(13)wvi=i,wvi=i+3k,wA=nk.
It is easy to see that the above elements of set are all different. It concludes the proof.Theorem 3.
SSnbe a subdivided star graph, and for everyn≥3,(14)rvsSSn=2n3.Proof.
LetSSn be a subdivided star graph with vertex set VSSn=A,xi,yi;1≤i≤n, VSSn=2n+1 and edge set ESSn=Ayi,xiyi,1≤i≤n,EHn=2n. The maximum degree of SSn is n. The graph SSn has one central vertex of degree n. Since the central vertex has degree of much greater than the other vertices, it must have a different vertex weight than the others. Based on Lemma 1, we have the following lower bound:(15)rvsG≥p+δ−1Δ+1=2n+1−12+1=2n3.
For the illustration of the vertex irregular reflexive,k-labeling of SS3 and SS4 can be depicted in Figure 2.
Furthermore, we will show the upper bound of vertex irregular reflexivek-labeling by defining the injection f and g. For n≥5, we have the following:(16)fA=0,fxi=0,if1≤i≤k,2i−k2,ifk+1≤i≤n.
Forn≡3,4mod6, we have the following function for yi and Ayi:(17)fyi=2n−k2,if1≤i≤k,2n−k2+2i−k2,ifk+1≤i≤n−1,2n−k2+2n−1−k2,ifi=n,gAyi=k−1,if1≤i≤n−2,k,ifn−1≤i≤n.
For otherwisen, we have(18)fyi=2n−k2,if1≤i≤k,2n−k2+2i−k2,ifk+1≤i≤ngAyi=k−1,if1≤i≤nforn≡5mod6,k,if1≤i≤nfor otherwise,gxiyi=i,if1≤i≤k,k−1,ifk+1≤i≤n,iodd forkevenandieven forkodd,k,ifk+1≤i≤n,ieven forkevenandiodd forkodd,where(19)k=2n3.
Based on the above injection, the overall vertex weight sets of the subdivided starSSn are(20)wxi=i,wyi=n+i,if1≤i≤n−2forn≡3,4mod6,2n−1,ifi=nforn≡3,4mod6,2n,ifi=n−1forn≡3,4mod6,n+i,if1≤i≤nfor otherwise,wA=nk−1+2,ifn≡3,4mod6,nk−1,ifn≡5mod6,nk,otherwise.
It is easy to see that the above elements of the set are all different. It concludes the proof.Figure 2
The illustration of labeling onSS3 and.SS4.Theorem 4.
LetBrn,mbe a broom graph, and for everyn≥2,n+1≤m,(21)rvsBrn,m=n+m3+1,ifn+m≡3mod6,n+m3,otherwise.Proof.
LetBrn,m be a broom graph with vertex set VBrn,m=A,vi,uj;1≤i≤n,1≤j≤m, VBrn,m=n+m+1, and edge set EBrn,m=Avi,1≤i≤n∪Aum∪ujuj+1,1≤j≤m−1,EHn=n+m.
The Broom graphBrn,m has n pendant vertices and one central vertex of degree n. Since the central vertex has a degree much greater than the other vertices, it must have a different vertex weight than the others. Based on Lemma 1, we have the following lower bound:(22)rvsBrn,m≥p+δ−1Δ+1=n+m3,for n+m≡3mod6, n+m=3k and k is odd. Since the vertices uj apart from vertex A have degree of at most 2, the labels of uj are n+m/3−1, and the label of edges, which are incident to uj, are n+m/3. Thus, the vertex weight uj is 3n+m/3−1=n+m−1. Furthermore, since the number of vertices of Broom graph is n+m, there must be at least two vertices with the same vertex weight. Thus, we need to add 1 on the sharpest lower bound:(23)rvsBrn,m≥n+m3+1,ifn+m≡3mod6.
Furthermore, we will show thatk is an upper bound of the reflexive vertex strength of Broom graph Brn,m. Let(24)k=n+m3+1,ifn+m≡3mod6,n+m3,otherwise.
Define an injectionf and g of the vertex irregular reflexive k-labeling of Broom graph rvsBrn,m as follows:(25)fA=k−1,ifkodd,k,ifkeven,fvi=0,if1≤i≤k,2i−k2,ifk+1≤i≤n+1,fu1=fvn+1,gAvi=i,if1≤i≤k,k−1,ifk+1≤i≤n+1,iodd forkevenandieven forkodd,k,ifk+1≤i≤n+1,ieven forkevenandiodd forkodd,gu1u2=gAvn+1.
Based on the above injection, the overall vertex weight sets ofBrn,m for vi;1≤i≤n+1 is(26)wvi=i,1≤i≤n+1.
Moreover, to determine label of verticesVG=uj,2≤j≤m and EG=Aum∪ujuj+1,1≤j≤m−1, we will use Algorithm 2.
It is easy to see that the above elements of setwvi and wuj are all different. It concludes the proof.Algorithm 2: The vertices’ and edges’ labels.
(1)
Given that the vertex weightVG=uj,2≤j≤m by wuj=n+j,2≤j≤m.(2)
Assign the labels of verticesuj by fuj=fU−j−1 and assign the labels of edges which are incident to uj by 1,2,3,…,k such that it meets with given vertex weight.(3)
When on point (ii), the label of edges is more thank, relabel the vertices with fuj=fuj−1+2 as well as relabel the edges which are incident to uj by 1,2,3,…,k such that it meets with given vertex weight wuj=n+j,2≤j≤m.(4)
STOP.


## 3. Concluding Remark

In this paper, we have studied the construction of the reflexive vertexk-labeling of any graph with pendant vertex. We have determined a sharp lower bound of the reflexive vertex strength of any graph G in Lemma 1, as well as obtained the exact value the reflexive vertex strength of any graph G in Theorem 1. By this lemma and theorem, we finally determined the reflexive vertex k-labeling of some families of graph with a pendant vertex. However, we need to find an upper bound of the reflexive vertex strength of any graph and study the reflexive vertex k-labeling of other families of graph or some graph operations. Therefore, we propose the following open problems:(1)
Determine an upper bound of reflexive vertex strength of any graph to find the gap between lower bound and upper bound, and continue to determine the exact values for reflexive vertex strength of any other special graphs(2)
Determine the construction of the reflexive vertexk-labeling of any regular graph, planar graph, or some graph operations



---

*Source: 7812812-2020-10-01.xml*