EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 13, No. 3, 2020, 674-696 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Efficient Zero Ring Labeling of Graphs Dhenmar E. Chua1,2,∗, Francis Joseph H. Campeña1, Floresto A. Franco Jr.1,3 1 Mathematics and Statistics Department, De La Salle University, Manila, Philippines 2 Mathematics and Physics Department, Adamson University, Manila, Philippines 3 Mathematics Department, Mariano Marcos State University, Batac, Ilocos Norte, Philippines Abstract. A zero ring is a ring in which the product of any two elements is zero, which is the additive identity. A zero ring labeling of a graph is an assignment of distinct elements of a zero ring to the vertices of the graph such that the sum of the labels of any two adjacent vertices is not the zero element in the ring. Given a zero ring labeling of a graph, if the cardinality of the set of distinct sums obtained from all adjacent vertices is equal to the maximum degree of the graph, then the zero ring labeling is efficient. In this paper, we showed the existence of an efficient zero ring labeling for some classes of trees and their disjoint union. In particular, we showed that an efficient zero ring labeling exists for some families of the following classes of trees: path graphs, star graphs, bistars, centipede graphs, caterpillars, spiders, lobsters, and rooted trees. We also showed results for other common classes of graphs. 2020 Mathematics Subject Classifications: 05C05, 05C25, 05C78 Key Words and Phrases: Efficient zero ring labeling, zero ring labeling, zero ring 1. Introduction Graph labeling is an assignment of labels to vertices or edges of a graph. Interesting questions naturally arise from this topic, so there has been a vast amount of literature that aimed to answer these questions while consequently introducing new problems. In 2014, Acharya et al [1] introduced zero ring labeling. In this labeling, each vertex is assigned a unique label from a zero ring such that the sum of any two adjacent vertices is not zero, i.e., the additive identity of the zero ring. It was proved that every graph admits a zero ring labeling with respect to some zero ring. The zero ring index of a graph, which is the smallest order of a zero ring in which the graph admits a zero ring labeling, was also studied for some well-known graphs. Pranjali et al [6] determined a necessary and sufficient condition for a finite graph of order n to attain an optimal zero ring index of n. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v13i3.3780 Email addresses: chuadhenmar@gmail.com (D. Chua), francis.campena@dlsu.edu.ph (F. Campeña), otserolf@yahoo.com (F. Franco) https://www.ejpam.com 674 c© 2020 EJPAM All rights reserved. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 675 Dela Rosa-Reynera [2] constructed optimal zero ring labelings for some classes of graphs. Included are labeling schemes for trees and cactus graphs. Moreover, the zero ring indices of graphs that result from some graph operations were also determined. In this paper, we extend the notion of zero ring labeling further. Can a zero ring labeling be constructed for a graph such that the number of distinct sums is equal to some number? In particular, we want to determine a zero ring labeling where this number is as small as possible. 2. Preliminaries 2.1. Basic definitions We now present some definitions used in this paper. For graph theory, [3, 5] are considered, while [4] is used for abstract algebra. Definition 1. A graph G = (V,E) is a pair of sets V and E such that E is a set of two-element subsets of V . The elements of V are the vertices of G, while the elements of E are the edges of G. The vertex set of a graph G is denoted by V (G), while its edge set is denoted by E(G). We say that e is an edge at v if v ∈ e. An edge {u, v} can be written as uv; we say that uv joins u and v, and u and v are the ends of uv. The number of vertices of a graph G is its order, denoted by |G|. The degree of a vertex v, denoted by d(v), is the number of edges at v. Two vertices u and v in a graph G are adjacent if uv is an edge in G. A graph G of order n is a complete graph, denoted by Kn, if for any two distinct vertices u and v in G, uv is an edge in G. Definition 2. The maximum degree of a graph G, denoted by ∆(G), is the highest degree of a vertex in G. Definition 3. A path in a graph is a subgraph P = [v1, v2, . . . , vn] such that V (P ) = {v1, v2, . . . , vn} and E(P ) = {v1v2, v2v3, . . . , vn−1vn}, where v1, v2, . . . , vn are distinct. The number of edges in a path is its length. In a path P = [v1, v2, . . . , vn], the vertices v1 and vn are the endvertices, while v2, v3, . . . , vn−1 are the inner vertices. Moreover, we say that P is a path between v1 and vn. The distance between two vertices u and v in a graph G is the length of the shortest path between u and v. Definition 4. A graph G is connected if for any vertices u and v in G, there is a path between u and v. A connected subgraph of a graph G is a component of G if it is not a proper subgraph of any other connected subgraph in G. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 676 2.2. Trees Definition 5. A tree is a connected graph with no cycle. The vertices of degree one in a tree are its leaves. Definition 6. A path graph Pn, where n ≥ 2, is a tree with two leaves and n−2 vertices with degree two. Definition 7. A star graph Sn, where n ≥ 1, is a tree with one vertex of degree n − 1 and all others with degree one. The vertex with the maximum degree in a star graph is its center. Definition 8. A bistar Bn, where n ≥ 1, is a graph formed by joining the centers of two star graphs Sn. Definition 9. An n-centipede, where n ≥ 1, is a tree with vertex set A ∪ B, where A = {a1, a2, . . . , an} and B = {b1, b2, . . . , bn}, and edge set E = {aibi : 1 ≤ i ≤ n} ∪ {aiai+1 : 1 ≤ i ≤ n− 1}. Definition 10. A caterpillar is a tree in which all vertices are within distance one of a central path. We define a hanging leaf of a vertex in the central path as a leaf that is adjacent to it but not a vertex in the central path. Example 1. The graph in Fig. 1 is a caterpillar with respect to any of the following central paths: [c, d, e, f ], [a, c, d, e, f ], [g, c, d, e, f ], [c, d, e, f, j], [a, c, d, e, f, j], or [g, c, d, e, f, j]. The hanging leaves of d are i, b, and h. c d e fc a c g d b d h d i f j Figure 1: A caterpillar Definition 11. A spider is a tree with a unique vertex of degree at least three and all others with degree at most two. We define the head of a spider as the vertex with the maximum degree and a leg as a component of the graph that is obtained by removing the head; that is, a leg is a path. Definition 12. A lobster is a tree in which all vertices are within distance two of a central path. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 677 We define an elbow of a vertex in the central path of a lobster as a vertex that is adjacent to it and whose distance from the central path is one. Moreover, we define a hanging leaf of an elbow as a vertex that is adjacent to it and whose distance from the central path is two. Definition 13. A rooted tree is a tree in which a particular vertex is designated as the root. The level of a vertex in a rooted tree is its distance from the root, and the height of a rooted tree is the maximum level of a vertex. A child (plural: children) of a vertex of level n in a rooted tree is an adjacent vertex whose level is n + 1. 2.3. Common classes of graphs We now define other common classes of graphs that are considered in this paper. Definition 14. A cycle graph Cn = [v1, v2, . . . , vn, v1] is a graph with vertex set V = {v1, v2, . . . , vn} and edge set E = {v1v2, v2v3, . . . , vn−1vn} ∪ {v1vn}, where n ≥ 3. Definition 15. A complete bipartite graph Km,n is a graph with vertex set V = {x1, x2, . . . , xm} ∪ {y1, y2, . . . , yn}, where m ≥ 1 and n ≥ 1, and edge set E = {xiyj : 1 ≤ i ≤ m and 1 ≤ j ≤ n}. Definition 16. A fan graph Fn is a graph that is obtained by joining all vertices of Pn to another vertex. Definition 17. A wheel graph Wn is a graph that is obtained by joining all vertices of Cn to another vertex. Definition 18. A friendship graph Tn is a graph that consists of n copies of C3 having exactly one common vertex. 2.4. Efficient zero ring labeling We now define a vertex labeling of a graph which was introduced by Acharya et al [1, 6] called zero ring labeling. Moreover, this paper introduces a variation of this vertex labeling called k-zero ring labeling and efficient zero ring labeling of graphs. In this study, the zero ring that will be used in the vertex labelings is the zero ring M0 2 (Zn). Definition 19. Let R be a ring with additive identity 0. If ab = 0 for any a, b ∈ R, then R is a zero ring. Let R be a ring with additive identity 0. We denote by M0 2 (R) the set of all 2 × 2 matrices of the form [ a −a a −a ] , a ∈ R. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 678 It can be verified that M0 2 (R) is a ring under matrix addition and matrix multiplication with additive identity [ 0 0 0 0 ] . Since for any a, b ∈ R,[ a −a a −a ] [ b −b b −b ] = [ ab− ab −ab + ab ab− ab −ab + ab ] = [ 0 0 0 0 ] , (1) M0 2 (R) is a zero ring. Since Zn is a ring, it follows that M0 2 (Zn) is a zero ring. We use Ai to denote the matrix [ i −i i −i ] , i ∈ Zn. Definition 20. Let G be a graph, and let R0 be a finite zero ring. An injective function f : V (G)→ R0 is a zero ring labeling of G if f(u) + f(v) 6= 0 for every uv ∈ E(G). Given a zero ring labeling, if the order of the zero ring is equal to the order of the graph, we say that the labeling is optimal. Example 2. Figure 2 shows a zero ring labeling of C5 using M0 2 (Z5). Since |C5| = |M0 2 (Z5)| = 5, this labeling is optimal. A3 A0 A1 A2 A4 Figure 2: Zero ring labeling of C5 using M0 2 (Z5) Given a graph G with zero ring labeling f , we consider the set K = {f(u) + f(v) : uv ∈ E(G)}. Since it was shown in [1] that every graph admits a zero ring labeling, we are interested in finding zero ring labelings for G such that |K| is as small as possible. Definition 21. Let G be a graph with zero ring labeling f , and let K = {f(u)+f(v) : uv ∈ E(G)}. A zero ring labeling f of G is a k-zero ring labeling if |K| = k. If |K| = ∆(G), then the zero ring labeling is efficient. Example 3. Figure 3 shows a 4-zero ring labeling of the diamond graph using M0 2 (Z8). In this labeling, the set of sums is K = {A1, A2, A5, A7} and thus |K| = 4. Figure 4 shows an efficient zero ring labeling of the butterfly graph G using M0 2 (Z10). In this labeling, the set of sums is K = {A2, A3, A7, A9} and thus |K| = ∆(G) = 4. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 679 A0 A2 A3 A7 A2 A7 Figure 3: 4-zero ring labeling of the diamond graph using M0 2 (Z8) A0 A2 A7 A0 A3 A9 Figure 4: Efficient zero ring labeling of the butter- fly graph using M0 2 (Z10) 3. Results Theorem 1. Let G be a graph, and let f : G → R0 be a zero ring labeling. If K = {f(u) + f(v) : uv ∈ E(G)}, then ∆(G) ≤ |K| ≤ |R0| − 1. Proof. Since f is a zero ring labeling, 0 /∈ K. Furthermore, R0 contains every sum f(u) + f(v) where uv ∈ E(G), hence K ⊂ R0 and |K| ≤ |R0| − 1. Let v ∈ V (G) and let N(v) = {v1, v2, . . . , vm} be the set of vertices that are adjacent to v. Since f is injective, it follows that the number of distinct sums f(v) + f(vi) for i = 1, 2, 3, . . . ,m generated from edges that end at v is equal to |N(v)| = m, which is the degree of v. Clearly, the maximum degree of G is the minimum number of elements of K. Theorem 2. If G is a graph with an efficient zero ring labeling, then any edge-induced subgraph H of G such that ∆(G) = ∆(H) has an efficient zero ring labeling. Proof. Let G be a graph with efficient zero ring labeling f : V (G) → R0, and let H be an edge-induced subgraph of G such that ∆(G) = ∆(H). Consider the restriction function f |H of f to the vertex set of H; that is, f |H(v) = f(v) for all v ∈ V (H). Since f is injective, f |H is injective. Also, 0 /∈ K = {f(u) + f(v) : uv ∈ E(G)} implies that 0 /∈ KH = {f |H(u) + f |H(v) : uv ∈ E(H)}. It remains to show that |KH | = ∆(H). Since ∆(G) = ∆(H), there exists at least one vertex v in V (G) where d(v) = ∆(G) such that v is also in H where d(v) = ∆(G). Then |KH | = ∆(G) = ∆(H). Theorem 3. Let G be a graph with n vertices, and let f : V (G) → R0 be a zero ring labeling. If f is optimal and ∆(G) = n− 1, then f is efficient. Proof. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is efficient, we need to show that |K| = n− 1. Since f is optimal, |R0| = n. By Theorem 1, ∆(G) ≤ |K| ≤ |R0| − 1. But ∆(G) = |R0| − 1 = n− 1. Therefore, |K| = n− 1. We now look at the efficient zero ring labeling of some classes of trees and other common classes of graphs. Theorem 4. Let G be a caterpillar in which each vertex in the central path has an equal number of hanging leaves. Then G has an efficient zero ring labeling. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 680 Proof. Let [w1, w2, . . . , wn] denote the central path of a caterpillar G and suppose that each wi, 1 ≤ i ≤ n, has r hanging leaves. Denote the hanging leaves of wi by wj i , where j = 1, 2, . . . , r. Case 1: Suppose n = 1. In this case, ∆(G) = d(w1) = r. Define a function f : V (G)→ M0 2 (Zr+1) such that f(w1) = A0 and f(wj 1) = Aj . Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = r and A0 /∈ K. For the set of sums, we obtain f(w1) + f(wj 1) = A0 + Aj = Aj 6= A0 (2) for j = 1, 2, . . . , r. Then A0 /∈ K. Moreover, K = {A1, A2, . . . , Ar} (3) and thus |K| = r. Therefore, f is an efficient zero ring labeling of G. Case 2: Suppose n = 2. In this case, ∆(G) = d(w1) = d(w2) = r+1. Define a function f : V (G)→M0 2 (Z2r+2) such that f(wi) = Ai(r+1) and f(wj i ) = A(i−1)(r+1)+j . Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = r + 1 and A0 /∈ K. For the set of sums, we obtain f(wi) + f(wj i ) = Ai(r+1) + A(i−1)(r+1)+j = A2ir+2i−r−1+j = Aj−r−1 (4) for j = 1, 2, . . . , r, and f(w1) + f(w2) = Ar+1 + A2r+2 = A3r+3 = Ar+1 6= A0 (5) It remains to show that Aj−r−1 6= A0 for j = 1, 2, . . . , r. By substitution, we obtain the sums A−r, A1−r, . . . , A−1, which are equal to Ar+2, Ar+3, . . . , A2r+1, respectively. For r + 2 ≤ m ≤ 2r + 1, we have 0 < m < 2r + 2, hence m 6≡ 0 (mod 2r + 2). Thus, Am 6= A0 for m = r + 2, r + 3, . . . , 2r + 1. Then A0 /∈ K. Moreover, K = {Ar+1, Ar+2, Ar+3, . . . , A2r+1} (6) and thus |K| = r + 1. Therefore, f is an efficient zero ring labeling of G. Case 3: Suppose n ≥ 3. In this case, ∆(G) = d(wi), where i 6= 1 and i 6= n. Then ∆(G) = r + 2. Define a function f : V (G)→M0 2 (Znr+n) such that f(wi) = A(r+1)( 2n−i−1 2 ) if i is odd A(r+1)( i−2 2 ) if i is even (7) and f(wj i ) = A(r+1)( i−3 2 )+j if i is odd A(r+1)( 2n−i−2 2 )+j if i is even . (8) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 681 Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = r + 2 and A0 /∈ K. For adjacent vertices in the central path, we obtain the sums f(wi) + f(wi+1) = A(r+1)( 2n−i−1 2 ) + A (r+1) ( (i+1)−2 2 ) = A(r+1)(n−1) (9) if i is odd, and f(wi) + f(wi+1) = A(r+1)( i−2 2 ) + A (r+1) ( 2n−(i+1)−1 2 ) = A(r+1)(n−2) (10) if i is even. Note that A(r+1)(n−1) 6= A0; otherwise, either r ≡ −1 (mod nr + n), which is a contradiction by definition of r, or n ≡ 1 (mod nr+n), which is also a contradiction by definition of n in this case. Similarly, A(r+1)(n−2) 6= A0. For pairs of adjacent hanging leaf and vertex in the central path, we obtain the sums f(wi) + f(wj i ) = A(r+1)( 2n−i−1 2 ) + A(r+1)( i−3 2 )+j = A(r+1)(n−2)+j (11) for j = 1, 2, . . . , r if i is odd, and f(wi) + f(wj i ) = A(r+1)( i−2 2 ) + A(r+1)( 2n−i−2 2 )+j = A(r+1)(n−2)+j (12) for j = 1, 2, . . . , r if i is even. We show that A(r+1)(n−2)+j 6= A0. Assume that A(r+1)(n−2)+j = A0 for some j. But this implies that j ≡ 2r + 2 (mod nr + n). This is a contradiction since n is at least 3 in this case, and j cannot be greater than r by its definition. Then A0 /∈ K. Moreover, K = {A(r+1)(n−2), A(r+1)(n−2)+1, . . . , A(r+1)(n−2)+r, A(r+1)(n−1)} (13) and thus |K| = r + 2. Therefore, f is an efficient zero ring labeling of G. Example 4. Figure 5 shows an efficient zero ring labeling of a caterpillar G with a central path with four vertices, where each vertex in the central path has three hanging leaves, using M0 2 (Z16). In this labeling, the set of sums is K = {A8, A9, A10, A11, A12} and thus |K| = ∆(G) = 5. Corollary 1. A path graph has an efficient zero ring labeling. Proof. Let G be the path graph Pn. Consider G as its own central path. Then G is a caterpillar with a central path with n vertices, where each vertex in the central path has no hanging leaf. By Theorem 4, G has an efficient zero ring labeling. Example 5. Figure 6 shows an efficient zero ring labeling of P10 using M0 2 (Z10). In this labeling, the set of sums is K = {A8, A9} and thus |K| = ∆(P10) = 2. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 682 A12 A0 A8 A4A12 A13 A12 A14 A12 A15 A0 A11 A0 A9 A0 A10 A8 A1 A8 A2 A8 A3 A4 A7 A4 A5 A4 A6 Figure 5: Efficient zero ring labeling of a caterpillar using M0 2 (Z16) A9 A0 A8 A1 A7 A2 A6 A3 A5 A4 Figure 6: Efficient zero ring labeling of P10 using M0 2 (Z10) Corollary 2. A star graph has an efficient zero ring labeling. Proof. Let G be the star graph Sn. Consider the center of G as its central path. Then G is a caterpillar with a central path with one vertex, and this vertex has n− 1 hanging leaves. Vacuously, each vertex in the central path of G has an equal number of hanging leaves. By Theorem 4, G has an efficient zero ring labeling. Example 6. Figure 7 shows an efficient zero ring labeling of S9 using M0 2 (Z9). In this labeling, the set of sums is K = {A1, A2, A3, A4, A5, A6, A7, A8} and thus |K| = ∆(S9) = 8. A0 A1 A0 A2 A0 A3 A0 A4 A0 A8 A0 A7 A0 A6 A0 A5 Figure 7: Efficient zero ring labeling of S9 using M0 2 (Z9) Corollary 3. A bistar has an efficient zero ring labeling. Proof. Let G be the bistar Bn. Consider the path joining the centers of the two star graphs Sn in G as its central path. Then G is a caterpillar with a central path with two vertices, where each vertex in the central path has n − 1 hanging leaves. By Theorem 4, G has an efficient zero ring labeling. Example 7. Figure 8 shows an efficient zero ring labeling of B9 using M0 2 (Z18). In this labeling, the set of sums is K = {A9, A10, A11, A12, A13, A14, A15, A16, A17} and thus |K| = ∆(B9) = 9. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 683 A9 A1 A9 A2 A9 A3 A9 A4 A9 A8 A9 A7 A9 A6 A9 A5 A9 A0A0 A10 A0 A11 A0 A12 A0 A13 A0 A17 A0 A16 A0 A15 A0 A14 Figure 8: Efficient zero ring labeling of B9 using M0 2 (Z18) Theorem 5. A centipede graph has an efficient zero ring labeling. Proof. Let G be an n-centipede. By definition of a centipede, we can find a central path in G such that each vertex in the central path has 1 hanging leaf. By Theorem 4, G has an efficient zero ring labeling. Example 8. Figure 9 shows an efficient zero ring labeling of a 6-centipede using M0 2 (Z12). In this labeling, the set of sums is K = {A8, A9, A10} and thus |K| = 3, which is the maximum degree of the graph. A10 A0 A8 A2 A6 A4A10 A11 A0 A9 A8 A1 A2 A7 A6 A3 A4 A5 Figure 9: Efficient zero ring labeling of a 6-centipede using M0 2 (Z12) Lemma 1. Let G be a caterpillar with at least 3 vertices. Then G is a caterpillar with respect to some central path [w1, w2, . . . , wn], where n ≥ 3 and w1 and wn have no hanging leaf. Proof. Let G be a caterpillar with at least 3 vertices, and let [v1, v2, . . . , vm] denote its central path. Suppose each vertex vi has ri hanging leaves, and let vji , where j = 1, 2, . . . , ri, denote the hanging leaves of vi. Consider v1, v2, . . . , vm as vertices in a central path P , along with v11 if r1 ≥ 1, and vrmm if rm ≥ 1. Thus, P is one of the following: [v1, v2, . . . , vm], [v11, v1, v2, . . . , vm], [v1, v2, . . . , vm, vrmm ], [v11, v1, v2, . . . , vm, vrmm ]. In any case, the number of vertices in P is at least three, and its endvertices have no hanging leaf. Clearly, each vertex in G is within distance one from P and thus G is a caterpillar with respect to central path P . Theorem 6. A caterpillar has an efficient zero ring labeling. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 684 Proof. Let G be a caterpillar with at least three vertices. By Lemma 1, G is a caterpillar with respect to some central path [w1, w2, . . . , wn], where n ≥ 3 and w1 and wn have no hanging leaf. For i = 2, 3, . . . , n− 1, suppose wi has ri hanging leaves, and let wj i , where j = 1, 2, . . . , ri, denote the hanging leaves of wi. Suppose rk is the maximum number of hanging leaves of a vertex in the central path; that is, rk ≥ ri for i = 2, 3, . . . , n− 1. Then ∆(G) = rk + 2. Consider a caterpillar H with a central path with n vertices, and where each vertex in the central path has rk hanging leaves. Let [v1, v2, . . . , vn] denote its central path, and let vji , where j = 1, 2, . . . , rk, denote the hanging leaves of vi. By Theorem 4, H has an efficient zero ring labeling h. Define a function f : V (G) → M0 2 (Znrk+n−rk) such that f(wi) = h(vi) and f(wj i ) = h(wj i ). Since h is injective, it follows that f is also injective. G is an edge-induced subgraph of H, so A0 /∈ KH = {h(u) + h(v) : uv ∈ E(H)} implies that A0 /∈ K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, it remains to show that |K| = ∆(G). Using the labeling in the proof of Theorem 4, we obtain K = {A(rk+1)(n−2), A(rk+1)(n−2)+1, . . . , A(rk+1)(n−2)+rk , A(rk+1)(n−1)}. (14) Thus, |K| = rk + 2 = ∆(G). Example 9. Figure 10 shows an efficient zero ring labeling of a caterpillar G with maximum degree ∆(G) = 6 using M0 2 (Z31). In this labeling, the set of sums is K = {A15, A16, A17, A18, A19, A20} and thus |K| = ∆(G) = 6. A0 A25 A5 A20 A10A0 A30 A0 A26 A0 A27 A25 A1 A5 A21 A5 A22 A20 A6 A20 A7 A20 A8 A20 A9 A10 A16 A10 A15 Figure 10: Efficient zero ring labeling of a caterpillar using M0 2 (Z31) Theorem 7. A spider has an efficient zero ring labeling. Proof. Let G be a spider with n legs, where n ≥ 3. Then ∆(G) = n. Let the head of G be denoted by w, and let w1 1, w 1 2, . . . , w 1 n denote the vertices that are adjacent to w. Suppose each leg containing w1 i has ri vertices, and let [w1 i , w 2 i , . . . , w ri i ] denote the leg containing w1 i . D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 685 Suppose rk = max{r1, r2, . . . , rn}. Define a function f : V (G) → M0 2 (Z(n−1)(2rk+1)) such that f(w) = A0, f(wj i ) = A (n−1) ( 2rk−j+1 2 ) +i−1 if j is odd A(n−1)( j 2)−i+1 if j is even (15) for i = 1, 2, . . . , n− 1, and f(wj n) =  A (n−1) ( 2rk+j+1 2 ) if j is odd A (n−1) ( 4rk−j+2 2 ) if j is even . (16) Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = n and A0 /∈ K. For pairs of adjacent head and vertex in a leg, we obtain the sums f(w) + f(w1 i ) = A0 + A (n−1) ( 2rk−1+1 2 ) +i−1 = A(n−1)(rk)+i−1 (17) for i = 1, 2, . . . , n− 1, and f(w) + f(w1 n) = A0 + A(n−1)(rk+1) = A(n−1)(rk+1) = A(n−1)(rk)+n−1. (18) Thus, we have the sums A(n−1)(rk), A(n−1)(rk)+1, A(n−1)(rk)+2, . . . , A(n−1)(rk)+n−2, A(n−1)(rk)+n−1. For adjacent vertices in a leg, we obtain the sums f(wj i ) + f(wj+1 i ) = A (n−1) ( 2rk−j+1 2 ) +i−1 + A(n−1)( j+1 2 )−i+1 = A(n−1)(rk+1) = A(n−1)(rk)+n−1 (19) if j is odd, and f(wj i ) + f(wj+1 i ) = A(n−1)( j 2)−i+1 + A (n−1) ( 2rk−(j+1)+1 2 ) +i−1 = A(n−1)(rk) (20) if j is even, for i = 1, 2, . . . , n− 1. Moreover, we have f(wj n) + f(wj+1 n ) = A (n−1) ( 2rk+j+1 2 ) + A (n−1) ( 4rk−(j+1)+2 2 ) = A(n−1)(3rk+1) = A(n−1)(rk) (21) if j is odd, and f(wj n) + f(wj+1 n ) = A (n−1) ( 4rk−j+2 2 ) + A (n−1) ( 2rk+(j+1)+1 2 ) = A(n−1)(3rk+2) = A(n−1)(rk+1) = A(n−1)(rk)+n−1 (22) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 686 if j is even. Then K = {A(n−1)(rk), A(n−1)(rk)+1, . . . , A(n−1)(rk)+n−2, A(n−1)(rk)+n−1}, (23) hence |K| = n. For m = 0, 1, 2, . . . , n − 1, it is clear that (n − 1)(rk) + m > 0 and (n − 1)(rk) + m < (n − 1)(rk) + (n − 1)(rk + 1) = (n − 1)(2rk + 1). Then A0 /∈ K. Therefore, f is an efficient zero ring labeling of G. Example 10. Figure 11 shows an efficient zero ring labeling of a spider with 4 legs using M0 2 (Z33). In this labeling, the set of sums is K = {A15, A16, A17, A18} and thus |K| = 4. A0 A15 A3 A12 A6 A9 A0 A16 A2 A13 A5 A0 A17 A1 A14 A0 A18 A30 A21 A27 A24 Figure 11: Efficient zero ring labeling of a spider using M0 2 (Z33) Lemma 2. Let G be a lobster with at least three vertices. Then G is a lobster with respect to some central path [v1, v2, . . . , vm], where m ≥ 3 and v1 and vm have no elbow. Proof. Let G be a lobster with at least three vertices, and let [w1, w2, . . . , wn] denote its central path. Suppose each vertex wi has ri elbows, and let wi,j , where j = 1, 2, . . . , ri, denote the elbows of wi. Suppose each elbow wi,j has si,j hanging leaves, and let wi,j,k, where k = 1, 2, . . . , si,j , denote the hanging leaves of wi,j . Consider w1, w2, . . . , wn as vertices in a central path P , along with w1,1 if r1 ≥ 1, w1,1,1 if s1,1 ≥ 1, wn,1 if rn ≥ 1, and wn,1,1 if sn,1 ≥ 1. Thus, P is one of the following: • [w1, w2, . . . , wn] • [w1,1, w1, w2, . . . , wn] • [w1,1,1, w1,1, w1, w2, . . . , wn] • [w1, w2, . . . , wn, wn,1] • [w1,1, w1, w2, . . . , wn, wn,1] • [w1,1,1, w1,1, w1, w2, . . . , wn, wn,1] • [w1, w2, . . . , wn, wn,1, wn,1,1,] D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 687 • [w1,1, w1, w2, . . . , wn, wn,1, wn,1,1] • [w1,1,1, w1,1, w1, w2, . . . , wn, wn,1, wn,1,1] In any case, the number of vertices in P is at least three, and its endvertices have no elbow. Clearly, each vertex in G is within distance two from P and thus G is a lobster with respect to central path P . Theorem 8. Let G be a lobster in which each elbow has at most one hanging leaf. Then G has an efficient zero ring labeling. Proof. Let G be a lobster with at least three vertices in which each elbow has at most one hanging leaf. By Lemma 2, G is a lobster with respect to some central path [w1, w2, . . . , wn], where n ≥ 3 and w1 and wn have no elbow. Clearly, each elbow has at most one hanging leaf with respect to this central path. Suppose each vertex wi has ri elbows, and let wi,j , where j = 1, 2, . . . , ri, denote the elbows of wi. If it exists, let wi,j,1 denote the hanging leaf of wi,j . Suppose rk is the maximum number of elbows of a vertex in the central path; that is, rk ≥ ri for i = 1, 2, . . . , n. Then ∆(G) = rk + 2. Define a function f : V (G) → M0 2 (Z2nrk+n−2rk) such that f(wi) = A(2rk+1)( 2n−i−1 2 ) if i is odd A(2rk+1)( i−2 2 ) if i is even , (24) f(wi,j) = A(2rk+1)( i−3 2 )+j if i is odd A(2rk+1)( 2n−i−2 2 )+j if i is even. , (25) and f(wi,j,1) = A(2rk+1)( 2n−i+1 2 )−j if i is odd A(2rk+1)( i 2)−j if i is even . (26) Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = rk + 2 and A0 /∈ K. For adjacent vertices in the central path, we obtain the sums f(wi) + f(wi+1) = A(2rk+1)( 2n−i−1 2 ) + A (2rk+1) ( (i+1)−2 2 ) = A(2rk+1)(n−1) (27) if i is odd, and f(wi) + f(wi+1) = A(2rk+1)( 2n−i−1 2 ) + A (2rk+1) ( 2n−(i+1)−1 2 ) = A(2rk+1)(n−2) (28) if i is even. Thus, there are only two distinct sums obtained for adjacent vertices in the central path. For pairs of adjacent elbow and vertex in the central path, we obtain the sums f(wi) + f(wi,j) = A(2rk+1)( i−2 2 ) + A(2rk+1)( i−3 2 )+j = A(2rk+1)(n−2)+j (29) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 688 for j = 1, 2, . . . , ri if i is odd, and f(wi) + f(wi,j) = A(2rk+1)( i−2 2 ) + A(2rk+1)( i−3 2 )+j = A(2rk+1)(n−2)+j (30) for j = 1, 2, . . . , ri if i is even. Since rk is the maximum number of elbows of a vertex in the central path, the obtained sums for pairs of adjacent elbow and vertex in the central path are A(2rk+1)(n−2)+1, A(2rk+1)(n−2)+2, . . . , A(2rk+1)(n−2)+rk . For pairs of adjacent hanging leaf and elbow, we obtain the sums f(wi,j) + f(wi,j,1) = A(2rk+1)( i−3 2 )+j + A(2rk+1)( 2n−i+1 2 )−j = A(2rk+1)(n−1) (31) if i is odd, and f(wi,j) + f(wi,j,1) = A(2rk+1)( 2n−i−2 2 )+j + A(2rk+1)( i 2)−j = A(2rk+1)(n−1) (32) if i is even. Thus, the sum of any pair of adjacent elbow and hanging leaf is equal. Then K = {A(2rk+1)(n−2), A(2rk+1)(n−2)+1, . . . , A(2rk+1)(n−2)+rk , A(2rk+1)(n−1)}, (33) hence |K| = rk + 2. To show that A0 /∈ K, it is sufficient to show that (2rk + 1)(n− 2), (2rk + 1)(n− 2) + 1, (2rk+1)(n−2)+2, . . . , (2rk+1)(n−2)+rk, (2rk+1)(n−1) are greater than 0 but less than 2nrk +n−2rk. The central path has at least 3 vertices, so n ≥ 3, and rk is at least zero by its definition. Then (2rk+1)(n−2)+m for m = 0, 1, . . . , rk and (2rk+1)(n−1) are greater than zero. Moreover, (2rk + 1)(n−2) +m < (2rk + 1)(n−2) + (2rk + 1) = (2rk + 1)(n−1) for m = 0, 1, . . . , rk. Since (2rk + 1)(n− 1) = (2rk + 1)(n)− 2rk− 1 < (2rk + 1)(n)− 2rk = 2nrk + n− 2rk, it follows that A0 /∈ K. Example 11. Figure 12 shows an efficient zero ring labeling of a lobster G in which each elbow has at most one hanging leaf. In this labeling, the set of sums is K = {A54, A55, A56, A57, A58, A63} and thus |K| = 6 = ∆(G). Theorem 9. Let G be a rooted tree whose root has the maximum degree. If the height of G is at most two, then G has an efficient zero ring labeling. Proof. Let G be a rooted tree of height two and with root w such that d(w) = n = ∆(G) = n. If n is one or two, then G is a caterpillar. Thus, by Theorem 6, G has an efficient zero ring labeling. Suppose n is at least three, and there exists at least one vertex of level two. Denote the children of w by w1, w2, . . . , wn. Since w has n children and ∆(G) = n, every child of w has at most n− 1 children. Suppose wi has ri children, and let wi,j , where j = 1, 2, . . . , ri denote the children of wi. Define a function f : V (G) → M0 2 (Z2n+1−1) such that f(w) = A0, f(wi) = A2i+1−3, and f(wi,j) =  A2i+j+1−2i+1 if i + j < n + 1 A2n+1−2i+1+3 if i + j = n + 1 A2n+1−2i+1+2i+j−n+1−1 if i + j > n + 1 . (34) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 689 A0 A54 A9 A45 A18A0 A63 A0 A55 A18 A36 A27 A54 A1 A62 A54 A2 A61 A54 A3 A9 A46 A9 A47 A9 A48 A45 A10 A53 A45 A11 A52 A45 A12 A51 A45 A13 A50 A18 A37 A26 A18 A38 A25 Figure 12: Efficient zero ring labeling of a lobster using M0 2 (Z64) Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, we need to show that |K| = ∆(G) = n and A0 /∈ K. For pairs of adjacent root and vertex of level one, we obtain f(w) + f(wi) = A0 + A2i+1−3 = A2i+1−3 (35) for i = 1, 2, . . . , n. Then we have the sums A1, A5, . . . , A2n+1−3. For pairs of adjacent vertex of level one and vertex of level two, we have three cases. Case 1: Suppose i + j < n + 1. Then we obtain f(wi) + f(wj i ) = A2i+1−3 + A2i+j+1−2i+1 = A2i+j+1−3. (36) Since each of i and j are at least one, we have the sums A2m+1−3 for m = 2, 3, . . . , n. These are A5, A13, . . . , A2n+1−3. Note that these sums are same with those from pairs of adjacent root and vertex of level one, only that A1 is not included. Case 2: Suppose i + j = n + 1. Then we obtain f(wi) + f(wj i ) = A2i+1−3 + A2n+1−2i+1+3 = A2n+1 = A1. (37) Thus, in this case, there is only one possible sum, which is A1. Case 3: Suppose i + j > n + 1. Then we obtain f(wi) + f(wj i ) = A2i+1−3 + A2n+1−2i+1+2i+j−n+1−1 = A2n+1+2i+j−n+1−4 = A2i+j−n+1−3. (38) Since i + j > n + 1, it follows that i + j is at least n+2. Also, i is at most n and j is at most n− 1, so i+ j is at most 2n− 1. Hence, 2i+j−n+1− 3 ≥ 2(n+2)−n+1− 3 = 23− 3 = 5 and 2i+j−n+1− 3 ≤ 2(2n−1)−n+1− 3 = 2n− 3. Then we have the sums A5, A13, . . . , A2n−3. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 690 It can be observed that these sums are same with those from pairs of adjacent root and vertex of level one, only that A1 and A2n+1−3 are not included. Therefore, K = {A1, A5, . . . , A2n+1−3}, (39) hence |K| = n. For m = 1, 5, . . . , 2n+1 − 3, it is also clear that m > 0 and m < 2n+1 − 1. Thus, A0 /∈ K. Example 12. Figure 13 shows an efficient zero ring labeling of a rooted tree G with a height of two. In this labeling, the set of sums is K = {A1, A5, A13, A29} and thus |K| = 4 = ∆(G). A0 A1 A0 A5 A0 A13 A0 A29 A1 A4 A1 A12 A1 A28 A5 A8 A5 A24 A5 A27 A13 A16 A13 A19 A13 A23 A29 A3 A29 A7 A29 A15 Figure 13: Efficient zero ring labeling of a rooted tree with a height of two using M0 2 (Z31) Theorem 10. Let G be a disjoint union of a finite number of caterpillars. Then G has an efficient zero ring labeling. Proof. Let G be a disjoint union of p caterpillars. We show that G has an efficient zero ring labeling. Case 1: The order of each caterpillar is one or two; that is, each caterpillar is either the trivial graph or P2. If all p caterpillars are trivial, then ∆(G) = 0. We label the vertices by A0, A1, A2, . . . , Ap−1. Clearly, the labeling is injective. Moreover, the set of sums is empty and thus A0 /∈ K. We are done. Suppose at least one caterpillar is not trivial. Then ∆(G) = 1. Let G1, G2, . . . , Gm denote the caterpillars with two vertices, and let Gm+1, Gm+2, . . . , Gp denote the trivial caterpillars, where 1 ≤ m ≤ p. Let V (Gi) = {wi−1, w2m−i+1} for i = 1, 2, . . . ,m, and let V (Gi) = {wi+m} for i = m + 1,m + 2, . . . , p. Define a function f : V (G) → M0 2 (Zm+p+1) such that f(wi) = Ai. Let K = {f(u) + f(v) : uv ∈ E(G)}. Clearly, f is injective. To show that f is an efficient zero ring labeling of G, we need to show that |K| = ∆(G) = 1 and A0 /∈ K. We obtain the sums f(wi−1) + f(w2m−i+1) = Ai−1 + A2m−i+1 = A2m (40) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 691 for i = 1, 2, . . . ,m. Then K = {A2m} and thus |K| = 1. Also, A2m 6= A0 since m > 0 and m < m + p + 1 ≤ m + m + 1 = 2m + 1. Case 2: The order of at least one caterpillar is at least three. Applying Lemma 1, we denote the vertices of each caterpillar such that the endvertices of the central path have no hanging leaf. Let G1, G2, . . . , Gp denote the caterpillars. Suppose the length of the central path of Gi has si vertices. Denote the central path of G1 by [w1, w2, . . . , ws1 ], and the central path of Gi by [wq+1, wq+2, . . . , wq+si ] for i = 2, 3, . . . , p, where q = s1 + s2 + · · ·+ si−1. Suppose the number of hanging leaves of wi is ri, and denote the hanging leaves of wi by wj i , where j = 1, 2, . . . , ri. Suppose the maximum number of hanging leaves of a vertex in G is rk. Since the endvertices in the central path of each caterpillar in G have no hanging leaf and there is at least one caterpillar with at least three vertices, it follows that ∆(G) = rk + 2. Consider a caterpillar H such that V (H) = V (G) and E(H) = E(G)∪{{wqi , wqi +1} : i = 1, 2, . . . p− 1}, where qi = s1 + s2 · · ·+ si. By Theorem 6, H has an efficient zero ring labeling h. Define a function f : V (G) → M0 2 (Znrk+n−rk) such that f(a) = h(a) for all a ∈ V (G). Since h is injective, it follows that f is also injective. G is an edge-induced subgraph of H, so A0 /∈ KH = {h(u) + h(v) : uv ∈ E(H)} implies that A0 /∈ K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, it remains to show that |K| = ∆(G) = rk + 2. Using the labeling in the proof of Theorem 4, we obtain K = {A(rk+1)(q−2), A(rk+1)(q−2)+1, . . . , A(rk+1)(q−2)+rk , A(rk+1)(q−1)}, (41) where q = s1 + s2 + · · ·+ sp. Thus, |K| = rk + 2 = ∆(G). Example 13. Figure 14 shows an efficient zero ring labeling of a disjoint union of three caterpillars using M0 2 (Z66). In this labeling, the set of sums is K = {A60, A61, A62, A63, A64, A65} and thus |K| = 6, which is the maximum degree of the graph. Theorem 11. Let G be a disjoint union of a finite number of lobsters in which each elbow has at most one hanging leaf. Then G has an efficient zero ring labeling. Proof. Let G be a disjoint union of p lobsters. We show that G has an efficient zero ring labeling. If the order of each lobster is one or two, then by Theorem 10, G has an efficient zero ring labeling. Suppose the order of at least one lobster is at least three. Applying Lemma 2, we denote the vertices of each lobster such that the endvertices of the central path have no hanging leaf. Let G1, G2, . . . , Gp denote the disjoint lobster graphs. Suppose the length of the central path of Gi has si vertices. Denote the central path of G1 by [w1, w2, . . . , ws1 ], and the central path of Gi by [wq+1, wq+2, . . . , wq+si ] for i = 2, 3, . . . , p, where q = s1+s2+· · ·+si−1. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 692 A0 A60 A5A0 A65 A0 A61 A0 A62 A60 A1 A60 A2 A5 A56 A5 A57 A5 A58 A5 A55 A50 A10 A50 A11 A50 A12 A50 A15 A20 A40 A25 A35A20 A45 A20 A41 A20 A42 A20 A43 A20 A44 A40 A21 A40 A22 A25 A36 A25 A37 A35 A26 A35 A27 A35 A30 Figure 14: Efficient zero ring labeling of a disjoint union of three caterpillars using M0 2 (Z66) Suppose the number of elbows of wi is ri, and denote the elbows of wi by wi,j , where j = 1, 2, . . . , ri. If it exists, denote the hanging leaf of wi,j by wi,j,1. Suppose the maximum number of elbows of a vertex in G is rk. Since the endvertices in the central path of each lobster in G have no elbow and there is at least one lobster with at least three vertices, it follows that ∆(G) = rk + 2. Consider a lobster H such that V (H) = V (G) and E(H) = E(G) ∪ {{wqi , wqi + 1} : i = 1, 2, . . . p− 1}, where qi = s1 + s2 · · ·+ si. By Theorem 8, H has an efficient zero ring labeling h. Define a function f : V (G) → M0 2 (Z2nrk+n−2rk) such that f(a) = h(a) for all a ∈ V (G). Since h is injective, it follows that f is also injective. G is an edge-induced subgraph of H, so A0 /∈ KH = {h(u) + h(v) : uv ∈ E(H)} implies that A0 /∈ K = {f(u) + f(v) : uv ∈ E(G)}. To show that f is an efficient zero ring labeling of G, it remains to show that |K| = ∆(G) = rk + 2. Using the labeling in the proof of Theorem 8, we obtain K = {A(2rk+1)(q−2), A(2rk+1)(q−2)+1, . . . , A(2rk+1)(q−2)+rk , A(2rk+1)(q−1)}, (42) where q = s1 + s2 + · · ·+ sp. Thus, |K| = rk + 2 = ∆(G). Example 14. Figure 15 shows an efficient zero ring labeling of a disjoint union of two lobsters using M0 2 (Z57). In this labeling, the set of sums is K = {A49, A50, A51, A52, A56} and thus |K| = 5, which is the maximum degree of the graph. Theorem 12. A cycle graph with n vertices has an efficient zero ring labeling if n is even. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 693 A49 A7 A42A49 A0 A49 A1 A49 A2 A7 A43 A7 A44 A42 A8 A42 A9 A42 A50 A42 A14 A21 A35 A21 A29 A21 A30 A21 A28 A0 A56 A1 A55 A2 A54 A8 A48 A9 A47 A10 A46 A44 A12 A29 A27 A30 A26 Figure 15: Efficient zero ring labeling of a disjoint union of two lobsters using M0 2 (Z57) Proof. Let Cn = [w1, w2, . . . , wn, w1], where n is even. Clearly, ∆(Cn) = 2. Define a function f : V (Cn)→M0 2 (Zn) such that f(wi) = { Ai−1 if i is odd An−i+3 if i is even . (43) Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(Cn)}. We obtain f(wi) + f(wi+1) = Ai−1 + An−(i+1)+3 = An+1 = A1 6= A0 (44) if i is odd, and f(wi) + f(wi+1) = An−i+3 + A(i+1)−1 = An+3 = A3 6= A0 (45) if i is even. Thus, K = {A1, A3}, hence |K| = 2 = ∆(Cn). Therefore, f is an efficient zero ring labeling of Cn. Example 15. Figure 16 shows an efficient zero ring labeling of C8 using M0 2 (Z8). In this labeling, the set of sums is K = {A1, A3} and thus |K| = 2 = ∆(C8). A1 A0A3 A6 A5 A4 A7 A2 Figure 16: Efficient zero ring labeling of C8 using M0 2 (Z8) D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 694 Theorem 13. A cycle graph with n vertices has no efficient zero ring labeling if n is odd. Proof. Let Cn = [w1, w2, . . . , wn, w1], where n is odd. Clearly, ∆(Cn) = 2. Assume that Cn has an efficient zero ring labeling f : V (Cn)→ R0. Since w1 and w2 are adjacent, f(w1) + f(w2) ∈ K = {f(u) + f(v) : uv ∈ E(Cn)}. It follows that f(w2) + f(w3) 6= f(w1) + f(w2); otherwise, f(w1) = f(w3), which is not possible since f is injective. K has only two elements, so K = {f(w1) + f(w2), f(w2) + f(w3)}. Similarly, f(w3) + f(w4) 6= f(w2) + f(w3). Then f(w3) + f(w4) = f(w1) + f(w2). Continuing in this manner, f(wn) + f(w1) would be equal to f(w1) + f(w2) since n odd. But this implies that f(w2) = f(wn). This is a contradiction since f is injective. Theorem 14. A complete bipartite graph has an efficient zero ring labeling. Proof. Let G = Km,n be a complete bipartite graph with vertex set {x1, x2, . . . , xm} ∪ {y1, y2, . . . , yn} and edge set {xiyj : 1 ≤ i ≤ m and 1 ≤ j ≤ n}. Without loss of generality, suppose m ≥ n. Then ∆(G) = m. Define a function f : V (G) → M0 2 (Z2m) such that f(xi) = A2i−2 and f(yj) = A2j−1. Clearly, f is injective. Let K = {f(u) + f(v) : uv ∈ E(G)}. We obtain f(xi) + f(yj) = A2i−2 + A2j−1 = A2i+2j−3 (46) for i = 1, 2, . . . ,m and j = 1, 2, . . . , n. Then K = {A1, A3, . . . , A2m−1}, hence |K| = m. Moreover, since m is at least one, A0 /∈ K. Thus, f is an efficient zero ring labeling of G. Example 16. Figure 17 shows an efficient zero ring labeling of K5,4 using M0 2 (Z10). In this labeling, the set of sums is K = {A1, A3, A5, A7, A9} and thus |K| = 5 = ∆(K5,4). A0 A1 A0 A3 A0 A5 A0 A7 A2 A1 A2 A3 A2 A5 A2 A7 A4 A1 A4 A3 A4 A5 A4 A7 A6 A1 A6 A3 A6 A5 A6 A7 A8 A1 A8 A3 A8 A5 A8 A7 Figure 17: Efficient zero ring labeling of K5,4 using M0 2 (Z10) Theorem 15. A fan graph Fn has an efficient zero ring labeling for n ≥ 3. Proof. It was shown in [2] that Fn has an optimal zero ring labeling for n ≥ 3. By definition of Fn, it has a vertex with degree |Fn| − 1. Thus, by Theorem 3, Fn has an efficient zero ring labeling for n ≥ 3. Theorem 16. A wheel graph Wn has an efficient zero ring labeling for n ≥ 3. D. Chua, F. Campeña, F. Franco / Eur. J. Pure Appl. Math, 13 (3) (2020), 674-696 695 Proof. It was shown in [2] that Wn has an optimal zero ring labeling for n ≥ 3. By definition of Wn, it has a vertex with degree |Wn| − 1. Thus, by Theorem 3, Wn has an efficient zero ring labeling for n ≥ 3. Theorem 17. A friendship graph Tn has an efficient zero ring labeling for n ≥ 2. Proof. It was shown in [2] that Tn has an optimal zero ring labeling for n ≥ 2. By definition of Tn, it has a vertex with degree |Tn| − 1. Thus, by Theorem 3, Tn has an efficient zero ring labeling for n ≥ 2. Example 17. Figure 18 shows an efficient zero ring labeling of F5 using M0 2 (Z6). Figure 19 shows an efficient zero ring labeling of W8 using M0 2 (Z8). Figure 20 shows an efficient zero ring labeling of T4 using M0 2 (Z9). In these labelings, the set of sums is the difference of the zero ring used and {A0}. A1 A2 A3 A4 A5 A0 A1 A0 A2 A0 A3 A0 A4 A0 A5 Figure 18: Efficient zero ring labeling of F5 using M0 2 (Z6) A2 A1A5 A8 A7 A6 A4 A3 A0 A1 A0 A5 A0 A8 A0 A7 A0 A6 A0 A4 A0 A3 A0 A2 Figure 19: Efficient zero ring labeling of W8 using M0 2 (Z9) A2 A1A8 A7 A6 A5 A4 A3 A0 A1 A0 A8 A0 A7 A0 A6 A0 A5 A0 A4 A0 A3 A0 A2 Figure 20: Efficient zero ring labeling of T4 using M0 2 (Z9) Acknowledgements The authors are grateful to the blind peer reviewers who helped improve the paper, as well as Dr. Severino V. Gervacio, Dr. Leonor A. Ruivivar, and Dr. Neil M. Mame who contributed invaluable comments and suggestions over the course of this study. REFERENCES 696 This work was funded by the Department of Science and Technology-Science Education Institute (DOST-SEI) and the Commission on Higher Education (CHED) of the Philippine government. References [1] Mukti Acharya, Pranjali, and Purnima Gupta. Zero ring labeling of graphs. Electronic Notes in Discrete Mathematics, 48:65–72, July 2015. [2] Michelle Dela Rosa-Reynera. On Graphs of Minimum Zero Ring Index. PhD thesis, August 2018. [3] Reinhard Diestel. Graph Theory. Springer, 4th edition, 2010. [4] Joseph A. Gallian. Contemporary Abstract Algebra. Brooks/Cole, 8th edition, 2013. [5] Frank Harary. Graph Theory. Addison-Wesley, 1969. [6] Pranjali, Mukti Acharya, and Purnima Gupta. Further results on zero ring labeling of graphs. Bulletin of the International Mathematical Virtual Institute, 5:205–210, 2014.