Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 214 https://internationalpubls.com Edge Irregularity Strength of Binomial Trees S. Muthukkumar1, K. Rajendran Vels Institute of Science Technology and Advanced Studies Chennai, India muthumed77@gmail.com, gkrajendra59@gmail.com Article History: Received: 28-01-2024 Revised: 16-04-2024 Accepted: 30-04-2024 Abstract: For a simple graph G, a vertex labeling φ: V (G) → {1, 2, · · ·, k} is called k- labeling. The weight of an edge uv in G, denoted by wφ(uv), is the sum of the labels of end vertices u and v. A vertex k-labeling is defined to be an edge irregular k- labeling of the graph G if for every two different edges e and f, wφ(e) ≠ wφ(f). The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G). In this paper, we prove that the edge irregularity strength of corona product of a tree T with K1 is es(T ∘ K1) = 2es(T). Further, we prove that the edge irregularity strength of binomial trees Bk is 2k−1, for k ≥ 1. Keywords: edge irregularity strength; corona product of graphs; binomial trees; 1. Introduction All the graphs considered in this paper are finite simple graphs. Terms that are not defined here can be referred from the book [10]. For a simple graph G, a vertex labeling φ: V (G) → {1, 2, · · ·, k} is called k-labeling. The weight of an edge uv in G, denoted by wφ(uv), is the sum of the labels of end vertices u and v. A vertex k-labeling is defined to be an edge irregular k- labeling of the graph G if for every two different edges e and f, wφ(e) ≠ wφ (f). The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G). In 1988, Chartrand et al. [4] introduced edge k-labeling δ of a graph G such that wδ(x) ≠ wδ(y) for all vertices x, y ∈ V (G) with x≠y. Such labelings were called irregular assignments and the irregularity strength s(G) of a graph G is known as the minimum k for which G has an irregular assignment using labels at most k. This parameter has attracted many researchers and several articles [2, 3, 6, 9] were published based on irregularity strength of graphs. In 2014, Ali Ahmad et al. [1] introduced a new parameter called edge irregularity strength of graphs. A vertex k-labeling φ: V (G) → {1, 2, · · ·, k} is called an edge irregular k- labeling of the graph if for every two different edges e and f there is wφ(e) ≠ wφ (f), where the weight of an edge e = xy ∈ E(G) is wφ(xy) = φ(x) + φ(y). The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G). For an exhaustive survey on edge irregularity strength of graphs, we refer to the dynamic survey on graph labeling by Gallian [7]. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 215 https://internationalpubls.com In [1], Ali Ahmad et al. proved that the lower bound for edge irregularity strength of a graph G is given by es(G) ≥ max {⌈ |𝐸(𝐺)|+1 2 ⌉ , ∆(𝐺)}. In this paper, we prove that the edge irregularity strength of corona product of a tree T with K1 is es (T ◦ K1) = 2es (T). Further, we prove that the edge irregularity strength of binomial trees Bk is 2k−1, for k ≥ 1. For all of our results proved in this paper, the edge irregularity strength of trees we proved attains its lower bound. 2 Corona Product of Graphs Let G and H be two graphs and let n be the order of G. The corona product, or simply the corona, of graphs G and H is the graph G ⊙ H obtained by taking one copy of G and n copies of H and then joining by an edge the ith vertex of G to every vertex in the ith copy of H. Given a vertex g ∈ G, the copy of H connected to g is denoted by Hg [8]. Complete graphs, stars and wheels are basic examples of corona product families. Observation 1: When G is a tree T with m edges and H ≅ K1, the corona T ◦ K1 is also a tree with 2m + 1 edges. Thus, the number of newly added vertices in the corona product of T and K1 will be m + 1 and all of those vertices are of degree 1. Notation: For the sake of convenience, let V (K1) = {w} and if u be any vertex in the tree T, then the corresponding vertex added in the corona product T ◦ K1 will be denoted as wu. In view of this notation, let us call the vertex u as the original vertex and the newly added vertex wu as the duplicate vertex for u. 3 Main Result In this section, we prove our main result. Theorem 1. Let T be a tree with edge irregularity strength be es(T ). Then es (T ◦ K1) = 2es (T). Proof. Let k = es (T) and φ: V (T) → {1, 2, · · ·, k} be the edge irregular k-labeling of T Case 1: k is even Let V1 be the set of vertices whose vertex labels are from the set {1, 2, · · ·, 𝑘 2 } and V2 be the set of vertices whose vertex labels are from the set { 𝑘 2 +1, · · ·, k}. Let us define the function ψ: V (T ◦ K1) → {1, 2, · · ·, 2k} as follows: For any vertex u in V1 ⊂ V (T), retain the vertex label for the corresponding vertex in T ◦ K1. That is, ψ(u) = φ(u), for any vertex u ∈ V1. For any vertex v in V2 ⊂ V (T), ψ(v) = φ(v) + k. At this stage, the original vertices of T ◦ K1 are all labeled by ψ. Let X be the set of all weights of original edges of T ◦ K1 as induced by ψ. Let W = {2, 3, · · ·, 2k} be the set of all weights of the edges. Let R = W − X be the required set of weights of edges. Let S be the sequence of arrangement of vertex labels in the increasing order as defined by ψ. Since T ◦ K1 is also a tree, we have the cardinality of the required set of weights of edges is equal to the length of the sequence S. Until R≠ϕ, choose a minimum weight (say r) in R and correspondingly choose the first term Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 216 https://internationalpubls.com (say q) in the sequence S. Now choose the original vertex with label q as defined by ψ in T ◦ K1 and label its duplicate vertex as r − q so that the induced weight of the newly added edge between the original vertex and its duplicate vertex will be r. Then, delete r from R and construct a new sequence S by deleting its first term q. This procedure can be done until R becomes an empty set. When R = ϕ, all the vertices have been labeled by the function ψ in T ◦ K1. Therefore, by the construction of T ◦ K1 and the definition of ψ, es (T ◦ K1) = 2k. Case 2: k is odd: Let V1 be the set of vertices whose vertex labels are from the set {1, 2, · · ·, ⌈ 𝑘 2 ⌉+ 1} and V2 be the set of vertices whose vertex labels are from the set {⌈ 𝑘 2 ⌉ +2, · · ·, k}. As defined for the even case, similarly we define ψ: V (T ◦ K1) → {1, 2, · · ·, 2k}. Therefore, either es (T) is odd or even, es (T ◦ K1) = 2es (T). 4 Binomial trees The binomial tree B0 consists of a single vertex. The binomial tree Bk is an ordered tree defined recursively. The binomial tree Bk consists of two binomial trees Bk−1 that are linked together: the root of one is the leftmost child of the root of the other. Note that there are 2k vertices in the binomial tree Bk. For more details about binomial trees refer [5]. 4.1 Edge Irregularity Strength of Binomial Trees In this section, we will calculate the edge irregularity strength of binomial trees. Observation 2: One can easily observe that corona product of binomial tree Bk−1 with K1 leads to the binomial tree Bk, for k ≥ 1. Thus, we have Bk−1 ◦ K1 = Bk. Theorem 2. Let Bk be the binomial trees for k ≥ 1. Then es (Bk) = 2k−1. Proof. We prove this by the method of induction on k ≥ 1. It is clear that es(B1) = 1 and es(B2) = 2. Let us assume that es (Bk−1) = 2k−2. Since binomial tree Bk = Bk−1 ◦K1 and using Theorem 1, we have es (Bk) = 2es (Bk−1) = 2.2k−2 = 2k−1. 5 Conclusion In this paper, we proved that the edge irregularity strength of corona product of a tree T with K1 is es (T ◦ K1) = 2es (T). Also, we proved that the edge irregularity strength of binomial trees Bk is 2k−1, for k ≥ 1. The edge irregularity strength of corona product of a tree and K1 attains its lower bound provided es (T) attains its lower bound. Further, the edge irregularity strength of binomial trees Bk attains its lower bound 2k−1. References [1] Ali Ahmad, Omar Bin Saeed Al-Mushayt, Martin Baca, On edge irregularity strength of graphs, Appl., Math., and Comput., 243, (2014), 607-610. [2] D. Amar, O. Togni, Irregularity strength of trees, Discrete Math. 190, (1998), 15–38. [3] T. Bohman, D. Kravitz, On the irregularity strength of trees, J. Graph Theory, 45, (2004), 241–254. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 2 (2024) 217 https://internationalpubls.com [4] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer., 64, (1988), 187–192. [5] Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Second edition, MIT Press. [6] A. Frieze, R.J. Gould, M. Karonski, F. Pfender, On graph irregularity strength, J. Graph Theory, 41, (2002), 120–137. [7] Gallian J.A., A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatorics, 22nd Edition, (2019), #DS6. [8] Farrugia R. and Harary F, On the corona of two graphs, Aequationes Math., 4, (1970), 322-325. [9] P. Majerski, J. Przybylo, On the irregularity strength of dense graphs, SIAM J. Discrete Math., 28 (1), (2014), 197–205. [10] West D.B., Introduction to Graph Theory, Prentice Hall of India, 2nd Edition, 2001.