SciresolSciresolhttps://indjst.org/author-guidelinesIndian Journal of Science and Technology0974-564510.17485/IJST/v15i14.254research articleSome New Classes of (k, d) Graceful 3 Distance Trees and 3 Distance Unicyclic GraphsMohantyGobind1MishraDebdas2SarangiPravat3BhattacharjeeSubarnasubarna.bhatt@gmail.com1Department of Mathematics, Ravenshaw UniversityCuttack, OdishaIndiaFormer Professor, C.V. Raman College of EngineeringBhubaneswar, OdishaIndiaDepartment of Statistics, Ravenshaw UniversityCuttack, OdishaIndia151463030120224320222022Abstract
Objectives: To identify a new family of (k,d) graceful graphs. Methods: The methodology involves mathematical formulation for labeling of the vertices of a given graph and subsequently establishing that these formulations give rise to (k,d) graceful labeling. Findings: Here we define a three-distance tree as the tree possessing a path such that each vertex of the tree is at most at a distance three from that path. In this paper we identify two families of three distance trees that possess (k,d) graceful labeling. Furthermore, we show that the three distance unicyclic graphs obtained from these three distance trees by joining two end vertices of their central paths are also (k,d) graceful. Novelty: Here, we give (k,d) graceful labeling to two new families of graphs, namely some classes of three distance trees and three distance unicyclic graphs. This effort is the first of its kind which involves exploration of 3-distance (k,d) graceful graphs.
Acharya and Hegde1 defined (k, d) − graceful labeling of a graph G with q edges as a surjective mapping of the vertex set of G into the set {0,1,2,...,k+(q-1)d} for some positive integers k and d. A (1,1)-graceful labeling is called a graceful labeling and a (k,1)-graceful labeling is called a k-graceful labeling. Bu and Zhang2 established that Km,n is (k,d)- graceful for all k and d and Kn is (k,d)-graceful if and only if k=d. Hegde and Shetty 3 showed that a tree T which can be transformed into a path by carrying out successive elementary transformations and the tree formed from T by subdividing each edge of T is (k,d)-graceful for all k and d. Some more results on graph labeling problems are found in some recent papers 4, 5, 6, 7, 8, 9, 10. For details of the literature involving (k, d) graceful graphs one may refer to the latest dynamic survey on graph labeling problems by Gallian 2.
From the literature survey it is found that there exist only some specific classes of graphs, namelyKm,n, Kn, and transformed trees which admit (k,d) graceful labeling. So, there is huge scope to explore in this area. In this paper we give (k, d)- graceful labeling to some new classes of three distance trees and three distance unicyclic graphs. Before deriving our results, we would like to have a recap of some of the existing graph theoretic terminologies and some new terminologies required for proving our results.
Definition 1.12 By a firecracker we mean a tree possessing a path known as the central path such that each vertex of the path is attached to the center of some star. Here we denote a firecracker by Pn⊙Kmi,1,1,.mi≥0,i=1,2,...,n,wheretheivertexofthepathPnis attached to the center of the starKmi,1.
Definition 1.2 A three distance tree T is a tree which contains a path H such that each vertex of T\H is at a distance at most three from H. We call the path H as the central path of T. Figure 1 represents a three-distance tree. A three distance unicyclic graph is a graph consisting of one cycle Cn such that each vertex of the graph is at distance at most three from Cn. Figure 2 represents a three distant unicyclic graph.
The three distance (k,d)-graceful trees in this paper are obtained by attaching leaves to the leaves and central path of firecrackers. The three distance unicyclic (k,d)- graphs in this paper are obtained by joining the end vertices of the central paths of three distance trees.
Here we use the method involving mathematical formulation for obtaining labeling of the vertices of a graph and then show that such a labeling is a (k ,d) - graceful labeling of that graph.
Results and Discussions
Constustion i 3.1 consider the fire crackerT=Pn⊙Kmi,1,1,.,i=1,2,...,n, whose vertices on the centralPnarec1,c2,c3,⋯,cn.The verticesT\Pnadjacent toci areci,i,i=1,2,...,nTci,i,areci,i,ji,ji=1,2,...,mi,i=1,2,...,n.Constructa 3-distance treeTby attaching leaves to the verticesci,i,jiand denote thembyci,i,ji,ti,ji,ti,ji=1,2,...,si,ji,wheresi,jiis the number of leaves adjacent toci,i,ji. All the verticesci,i,jineed not be attached to leaves. Say, out ofmivertices attached toci,i,,riof the mattached to leaves. Letr=maxi=1nri.Assume thatmi≥rfor eachi. Let ET=q. Obviously, q=2n-1+∑i=1nmi+∑jirisi,ji.
Theorem 3.1 The three distant trees in Construction 3.1 admit (k,d) graceful labeling with d∤k.
Proof: Consider the three distant trees T in Construction 3.1. Define the mapping f:V(T)-→{0,1,2,3,4,…,k+(q-1)d} as follows.
For i=1,2,...,n,fci=i-1r+22difiisoddk+q-i2r+2difiiseven
We find that g(u,v) assumes values {k,k+d,k+2d,...,k+(q-1)d}. Therefore, the labels of the edges of T constitute the set {k,k+d,k+2d,...,k+(q-1)d} and hence the mapping f is a (k,d) graceful labeling of T, i.e. T is a (k,d) graceful tree with d∤k. �
Theorem 3.2 The three distant unicyclic graphs obtained from the three distant trees in Construction 3.1 by joining the vertices c1 and cn admit (k,d)graceful labeling with d∤kifn≡(0mod4).
Proof: Consider the three distant unicyclic graph G in Theorem 3.2. Define the mapping
f:V(G)-→{0,1,2,3,4,,k+(q-1)d} as follows.
For i=1,2,…,n,pi=1,2,⋯,li,ji=1,2,⋯,mi,ti,ji=1,2,⋯,si,ji,
Find that g(u,v) assumes values {k,k+d,k+2d,...,k+(q-1)d}. Therefore, the labels of the edges of T constitute the set {k,k+d,k+2d,...,k+(q-1)d} and hence the mapping fis a (k,d) graceful labeling of G, i.e. G is a (k,d) graceful graph when d∤k. �
Theorem 3.3: The 3-distance tree derived from the 3-distance tree in Theorem 3.1 with some or all vertices of Pnattached to some leaves is (k,d) graceful with d∤k.
Proof: Let T be a tree derived from the 3-distance tree in Theorem 3.1 with some or all the vertices of Pn may be adjacent to some leaves. Let the vertices on the central path Pn be c1,cn,⋯,cn. Let ci be attached to li leaves apart from the vertex ci,i. Let the li leaves adjacent to ci be xi,pi,pi=1,2,...,li. The remaining descriptions and notations involving the tree T are the same as those in Theorem 3.2. Define the mapping f:V(T)-→{0,1,2,3,4,,k+(q-1)d} as follows.
For i=1,2,…,n,pi=1,2,⋯,li,ji=1,2,⋯,mi,ti,ji=1,2,⋯,si,ji,
Find that g(u, v) assumes values {k,k+d,k+2d,...,k+(q-1)d}. Therefore, the labels of the edges of T constitute the set {k,k+d,k+2d,...,k+(q-1)d} and hence the mapping f is a (k,d) graceful labeling of T, i.e. T is a (k,d) graceful tree with d∤k. �
Theorem 3.4 The three distant unicyclic graphs obtained from the three distant trees in Theorem 3.4 by joining the vertices c1 and cn admit (k,d) graceful labeling with d∤k if n≡(0mod4).
Proof: Consider the three distant unicyclic graph G in Theorem 3.4. Define the mapping
f:V(G)-→{0,1,2,3,4,,k+(q-1)d} as follows.
For i=1,2,…,n,pi=1,2,⋯,li,ji=1,2,⋯,mi,ti,ji=1,2,⋯,si,ji,
Find that g(u,v) assumes values {k,k+d,k+2d,...,k+(q-1)d}. Therefore, the labels of the edges of T constitute the set {k,k+d,k+2d,...,k+(q-1)d} and hence the mapping fis a (k,d) graceful labeling of G, i.e. G is a (k,d) graceful graph when d∤k.
A three distance tree of the type in Theorem 3.1 with a graceful labeling. Here \begin{aligned}
&n=8, m_{1}=5, m_{2}=5, m_{3}=5, m_{4}=5, m_{5}=5, m_{6}=5, m_{7}=5, m_{8}=5, r= \\
&3, s_{1,1}=5, s_{4,1}=1, s_{5,1}=1, s_{5,2}=1, s_{6,1}=1, s_{6,2}=5, s_{7,1}=4, s_{7,2}=2, s_{8,1}= \\
&1, s_{8,2}=5, s_{8,3}=1
\end{aligned}
A three distance unicyclic graph of the type in Theorem 3.2 with a (k,\;d)\;graceful labeling. Here n=8, m_{1}=5, m_{2}=3, m_{3}=4, m_{4}=5, m_{5}=5, m_{6}=5, m_{7}=
5, m_{8}=5, r=3, s_{1,1}=5, s_{2,1}=2, s_{3,1}=1 s_{4,1}=1, s_{5,1}=1, s_{5,2}=1, s_{6,1}=
1, s_{6,2}=5, s_{7,1}=4, s_{7,2}=2, s_{8,1}=1, s_{8,2}=5, s_{8,3}=1
A three distance tree of the type in Theorem 3.3 with a (k,\;d) graceful labeling. Here n\;=\;8,\;m_1=\;5,\;m_2\;=\;3,\;m_3=\;3,\;m_4=\;4,\;m_5=\;3,\;m_6\;=\;4,\;m_7=\;4,\;m_8=\;5,\;r\;=\;3,\;s_{1,1}=\;5,{\;s}_{3,1}=\;2,{\;s}_{3,2}=\;1,{\;s}_{3,3}=\;1,{\;s}_{5,1}=\;1,\;s_{5,2}=\;1,{\;s}_{6,1}=\;\;4,\;s_{6,2}=\;1,{\;s}_{7,1}=\;2,\;s_{7,2}=\;4,{\;s}_{8,1}=\;3,{\;s}_{8,2}=\;3,\;s_{8,3}=\;1,{\;l}_1=\;1,{\;l}_2=\;1,\;l_3=\;2,\;l_4=\;0,\;l_5=\;1,{\;l}_6=\;2,{\;l}_7=\;2,\;l_8=\;0.
A three distance unicyclic graph of the type in Theorem 3.4 with a (k,\;d) graceful labeling. Here n\;=\;8,\;m_1=\;5,\;m_2\;=\;3,\;m_3=\;3,\;m_4=\;4,\;m_5=\;5,\;m_6\;=\;4,\;m_7=\;4,\;m_8=\;4,\;r\;=\;3,\;s_{1,1}=\;4,{\;s_{2,1}=\;1,s}_{3,1}=\;1,{\;s}_{5,1}=\;1,\;s_{5,2}=\;1,{\;s}_{6,1}=\;\;5,\;s_{6,2}=\;1,{\;s}_{7,1}=\;4,\;s_{7,2}=\;2,{\;s}_{8,1}=\;3,{\;s}_{8,2}=\;2,\;s_{8,3}=\;4,{\;l}_1=\;2,{\;l}_2=\;1,\;l_3=\;2,\;l_4=\;0,\;l_5=\;0,{\;l}_6=\;3,{\;l}_7=\;2,\;l_8=\;0.
Conclusion
In this article we give \begin{pmatrix}k&d\end{pmatrix} graceful labeling to a class three distance trees which are obained from a firecracker by attaching leaves either to the leaves of the firecracker or the vertices on the central path of the firecracker or both. Find that in Construction 3.1 we assume the condition that m_{i} \geq rfor each i Moreover, here we give \begin{pmatrix}k&d\end{pmatrix} graceful labeling to a class of three distance unicyclic graphs obtained by joining end vertices of the central path of a \begin{pmatrix}k&d\end{pmatrix} graceful three distance tree mentioned above. Our effort is the first of its kind where we give \begin{pmatrix}k&d\end{pmatrix}graceful labeling to a family of three distance three and three distance unicyclic graph. However, the future advancement of this result requires to cover all three distance trees and three distance unicyclic graphs, i.e., by generalizing our results dropping the assumption m_{i\;\geq\;r}for each i_{}
ReferencesAcharyaB. D.HegdeS. M.Arithmetic graphs19901432752990364-9024, 1097-0118Wileyhttps://dx.doi.org/10.1002/jgt.3190140302GallianJ AA dynamic survey of graph labeling2021http://www.combinatorics.org/Surveys/ HegdeS MShettySSequential and magic labeling of a class of trees200124137141https://www.researchgate.net/profile/Suresh-Hegde/publication/266240373_Sequential_and_magic_labeling_of_a_class_of_trees/links/5f1477d7299bf1e548c37269/Sequential-and-magic-labeling-of-a-class-of-trees.pdfS MahendranMuruganKPentagonal Graceful Labeling of Some Graphs202115598112http://www.worldscientificnews.com/wp-content/uploads/2021/02/WSN-155-2021KumarSSrirajM AHegdeSuresh M.Hegde, graceful labeling of digraphs-a survey202118143147https://doi.org/10.1080/09728600.2021.1978014SankariR SNisayaM P Syed AliHigher order triangular graceful labeling of some graphs20211564061http://www.worldscientificnews.com/wp-content/uploads/2021/03/WSN-156-2021-40-61.pdf.DeenM R Z ElG ElmahdyNew classes of graphs with edge δ− graceful labeling202273554358910.3934/math.2022197KananiJ CKaneriaV JGraceful labeling for some snake related graphs2021711243255https://bharataganitaparisad.com/wp-content/uploads/2021/10/711-ch025.pdfYehR KA note on n-set distance-labelings of graph2021110355602161-763510.4236/ojdm.2021.113005Scientific Research Publishing, Inc.KumarAjayKumarAjendraKumarVipinKumarKameshGraceful distance labeling for some particular graphs2021915575612319-3786, 2321-5666MKD Publishing Househttps://dx.doi.org/10.26637/mjm0901/0094