EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 4, 2024, 3492-3516 ISSN 1307-5543 – ejpam.com Published by New York Business Global Orthogonal Decompositions of Regular Graphs and Designing Tree-Hamming Codes Hanan Shabana1,∗, Ramadan El-Shanawany1, Sahar Halawa2 1 Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Egypt. 2 Department of Mathematics, Faculty of Education, Ain Shams University, Egypt. Abstract. The paper introduces the concept of graph decomposition. That is orthogonal de- compositions. Orthogonal decompositions of a graph H are a partitioning H into subgraphs of H such that any two subgraphs intersect in at most one edge. These decompositions are called G−orthogonal decompositions of H if and only if every subgraph in such decompositions is isomor- phic to the graph G. Such decomposition appears in a lot of applications; statistics, information theory, in the theory of experimental design, and many others. An approach of constructing or- thogonal decompositions of regular graphs is introduced here. Application to this approach for constructing tree – orthogonal decompositions of complete bipartite graphs is considered. Further, the use of orthogonal decompositions for designing tree hamming codes is also discussed along with examples. The study shows that such codes have efficient properties when used to detect and cor- rect the errors that may occur during the transmission of data through a network. Furthermore, we present a method for the recursive construction of orthogonal decompositions. 2020 Mathematics Subject Classifications: 05B30, 0570, 94A60, 94A62 Key Words and Phrases: Graph decomposition; Orthogonal cover; Bipartite graph; Hamming codes 1. Introduction All graphs being discussed here are undirected, finite, and do not have loops or mul- tiple edges. For standard graph-theoretic terminology, we refer to [1]. A decomposition of a graph H is a set of edge-disjoint subgraphs of H whose union gives the graph H. Thus, we say that the set G = {G1, G2, · · · , Gk} of k subgraphs of H decompose H if and only if k⋃ i=1 Gi = H (ignoring isolated vertices) & k⋂ i=1 Gi = ϕ(empty graph). If Gi ≊ G for each i ∈ {1, 2, · · · k} , then G is called a decomposition of H by G. Throughout the paper we use ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5353 Email addresses: hananshabana22@gmail.com (H. Shabana), ramadan.elshanawany380@gmail.com (R. El-Shanawany), saharreda@edu.asu.edu.eg (S. Halawa) https://www.ejpam.com 3492 Copyright: © 2024 The Author(s). (CC BY-NC 4.0) H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3493 V (X), E(X) for the vertex set and edge set of the graph X respectively, Pk for a path of k vertices, mG for m disjoint copies of G, and G∪H for disjoint union of graphs G and H. Let G1 = {G1, G2, · · · , Gk} and G2 = {F1, F2, · · · , Fk} be two distinct edge decompositions of H by G such that for each i ∈ {1, 2, · · · k} , Gi ≊ G ≊ Fi. Such two decompositions are called orthogonal decompositions if |E(Gi) ∩ E(Fj)| = 1 for all i, j ∈ {1, 2, · · · k} . Whence, the collection {G1 ∪ G2} is equivalent to an orthogonal double cover (ODC) of H by G. An ODC of H by G is a collection F = {ϕ (x) : x ∈ V (H)} of subgraphs of H all isomorphic to the graph G, such that every edge of H belongs to exactly two elements from F and any two elements ϕ (x1) and ϕ (x2) from F have a common edge if and only if the edge (x1, x2) ∈ E(H). Not all graphs H have an ODC. The necessary condition to find an ODC of H is that the graph H is regular. For the complete graph Kn, ODC is extensively studied, we refer the reader to a survey [14]. ODC of Cayley graphs was studied in [6, 7, 10]. An ODC F of H is cyclic (CODC) if the cyclic group of order |V (H)| is a subgroup of the automorphism group of H ( the group of automorphism of the graph H which preserves the covering) [16]. Sampathkumar et al. [20] investigated CODCs of circulant graphs by 4-regular circulant graphs. In [11], the authors attacked the problem of the existence of ODCs of 2-regular graphs and 3-regular graphs. Sampathkumar et al. [21] presented σ−labeling, as a special category of orthogonal labeling. Using σ−labeling, they constructed CODCs of circulant graphs by some caterpillars of diameters 4. Higazy et al. [22] gave a complete classification for circulant graphs of degree five which lead to an ODC by some graphs. The present paper is interested in studying ODC for balanced complete bipartite graph Kn,n. Given a positive integer n, the balanced bipartite graph Kn,n is a bipar- tite graph with a 2n−element vertex set V . This set V is divided into two partite sets of vertices, each containing n elements. The vertices of Kn,n are labeled by the ele- ments of Zn × {0, 1} where Zn = {0, 1, 2, · · · , n − 1} represents all residue classes mod- ulo n. The edge set of Kn,n is defined as pairs E(Kn,n) = {((u, 0), (v, 1)) ; u, v ∈ Zn}. For simplicity and if there is no danger of ambiguity,we use vr for the vertex (v, r) ∈ Zn×{0, 1}, and (u0, v1) for the edge ((u, 0), (v, 1)) . We aim to construct an ODC of Kn,n by G where G is isomorphic to certain trees with n edges. In the next section, we introduce the fundamentals of our approach for constructing an ODC of Kn,n. We call this approach a base-generated approach (BGA). Section 3, shows the construction of ODCs of Kn,n by certain trees based on BGA introduced in Section 2. An application of BGA in designing graph error detecting and correcting codes is presented in Section 4. Section 5 introduces a recursive construction of ODC of higher order balanced com- plete bipartite graph by disjoint trees. The conclusion of the paper and future work are presented in Section 6. 2. Fundamentals of base-generated approach To construct an ODC of Kn,n we have to find two orthogonal decompositions of Kn,n. In base-generated approach (BGA) we first seek to find the base for each decomposition. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3494 Then ODC is generated from such two bases. Let us introduce the principals of this approach. Assume e = (a0, b1) be an edge belonging to E(Kn,n).The length of the edge e is defined by d(e) = b− a, where addition and subtraction are calculated modulo n. Definition 1. Let G to be a subgraph of Kn,n, and s ∈ Zn. Then the graph G+s (or Gs) with E(G+ s) = {((a+ s)0 , (b+ s)1); (a0, b1) ∈ E(G)} is called s- translation of G. Definition 2. A subgraph G of Kn,n is called a base of an edge decomposition of Kn,n by G if and only if n−1⋃ s=0 {E (G+ s)} = E (Kn,n) . The next theorem proves the validity of the method by which we build a base. Theorem 1. Let G be a subgraph of Kn,n such that |E(G)| = n. Then G is a base of an edge decomposition of Kn,n by G if all the edges of G are mutually different in lengths, i.e.{d(e); e ∈ E(G)} = Zn. Proof. Let X = {(ai, bi) ; i ∈ Zn} be the set of all edges of G, such that the edge ei = (ai, bi) . Since all the edges of G are mutually different in lengths, then the set X satisfies {bi − ai ; i ∈ Zn} = Zn. Let di = bi − ai that is a unique for every edge (ai, bi) ∈ E(G); i ∈ Zn. For any s, t ∈ Zn and s ̸= t, let (ai + s, bi + s) ∈ E(Gs) and (ai + t, bi + t) ∈ E(Gt). Assume that |E(Gs) ∩ E(Gt)| ≠ 0, that is there is at least one edge (ai, bi) ∈ |E(Gs) ∩ E(Gt)| . From the definition of s- translation of G, we know that (ai + s− s, bi + s− s) = (ai, bi) . Also (ai + t− t, bi + t− t) = (ai, bi) . Since bi − ai = di is unique for every edge (ai, bi) ∈ E(G), then we have a contradiction. Therefore, |E(Gs) ∩ E(Gt)| = 0 for any s, t ∈ Zn and s ̸= t. Moreover, n−1⋃ i=0 {E (Gi)} = E (Kn,n) , thus G is a base of an edge decomposition of Kn,n by G. 2.1. Construction of an ODC of Kn,n using two orthogonal bases Let G1 and G2 be two bases of two decompositions of Kn,n. Such two bases are orthogonal if |E(G1) ∩ E(G2)| = 1. If two bases G1 and G2 are orthogonal, then the collection G ={Gi a : a ∈ Zn, i ∈ {1, 2}} with Gi a = (Gi + a) is equivalent to an ODC of Kn,n. Moreover, G represents an ODC of Kn,n by G if G1 ≊ G ≊ G2. Definition 3. Let G to be be a subgraph of Kn,n, the subgraph G ′ of Kn,n with E(G ′ ) = {{a0, b1} : {b0, a1} ∈ E(G)} is called the symmetric graph of G. Remark 1. The graph G ′ is a base of a decomposition of Kn,n by G if and only if G is also a base of a decomposition of Kn,n by G. in the next section, we use an algebraic representation for a base G of a decomposition of Kn,n. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3495 2.2. Bases representation The representation of the base G is given by the ordered n-tuple v(G) = (v0, v1, · · · , vn−1) ∈ Zn × Zn × · · · × Zn︸ ︷︷ ︸ n times such that vi ∈ Zn for all i ∈ {0, 1, 2, · · · , n− 1} and (vi)0 is the unique vertex ((vi, 0) ∈ Zn×{0}) that belongs to the unique edge of length i in G. The edge set of G is E(G) = {((vi)0 , (vi + i)1); 0 ≤ i ≤ n− 1} . For instance, the base in Figure 1 is represented by the vector v(P4) = (0, 1, 1), (e.g. (10,01) is the unique edge of length 2, thus v2 = 1). If G is a base, we will call also v(G) a base. Figure 1: The base P4 in K3,3 with the length of each edge, where v(P4) = (0, 1, 1). Definition 4. Let v(G1) and v(G2) be two different bases in Kn,n. Then, G1 and G2 are orthogonal if and only if {vi(G1)− vi(G2) : i ∈ Zn} = Zn. Theorem 2. If G1 0 and G2 0 are the orthogonal bases in Kn,n, then the collections G1={G1 0+x : x ∈ Zn} and G2={G2 0+y : y ∈ Zn} with ( Gi 0+x = (Gi 0 + x) ) and ( Gi 0+y = (Gi 0 + y) ) for i ∈ {1, 2} represent an ODC of Kn,n. Proof. Since G1 0 and G2 0 are bases then each collection from the collections G1={G1 0+x : x ∈ Zn} and G2={G2 0+y : y ∈ Zn} forms an edge decomposition of Kn,n. Assume that the edge {a0, b1} ∈ E(Kn,n). Then there are exactly two graphs G1 x and G2 y from the collections G1 and G2 such that {a0, b1} ∈ E(G1 x) and {a0, b1} ∈ E(G2 y). Moreover, for any x, y ∈ Zn and s, t ∈ {1, 2}, ∣∣E(Gs 0+x) ∩ E(Gt 0+y) ∣∣ = 0 whenever s = t. Besides that, there is a unique vi satisfies vi(G 1 0) − vi(G 2 0) = b − a and vi(G 1 0) + a = vi(G 2 0) + b. Thus, there is exactly one edge l = {(vi(G0) + a)0 , (vi(G0) + a+ vi)1} ∈ E(G1 0+x) and l = {(vi(G1) + b)0 , (vi(G1) + b+ vi)1} ∈ E(G2 0+y). Thus, ∣∣E(Gs 0+x) ∩ E(Gt 0+y) ∣∣ = 1 whenever s ̸= t. Hereafter, we show a method by which we can construct an ODC of Kn,n using only one base instead of two bases. Definition 5. A base G is called a symmetric base with respect to Zn if v(G) and v(G ′ ) are orthogonal. The following theorem introduces the condition for a symmetric base. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3496 Theorem 3. A base G in Kn,n represented by the vector v(G) = (v0, v1, · · · , vn−1) is called a symmetric base if it satisfies {vi − v−i + i} = Zn for all i ∈ Zn. Proof. Since G is a base in Kn,n.The graph G ′ is also a base in Kn,n represented by v(G ′ ). Let the edge e = { vi(G ′ ), vi(G ′ ) + i } ∈ E ( G ′ ) such that the length of e equals i. Following the definition of a symmetric graph, the edge { vi(G ′ ) + i, vi(G ′ ) } of length −i will belong to E (G) . Whence, v−i(G) = vi(G ′ )+ i, which means that vi(G ′ ) = v−i(G)− i. Following Definition 4, v(G) and v(G ′ ) are orthogonal if { vi(G)− vi(G ′ ); i ∈ Zn } = Zn. Then the necessary and sufficient condition for the orthogonality of the bases G and G′ is {vi(G)− v−i(G) + i; i ∈ Zn} = Zn. Since G ′ is the symmetric graph of G, then the base G is a symmetric base with respect to Zn if and only if {vi(G)− v−i(G) + i; i ∈ Zn} = Zn. Theorem 3 yields the next theorem. Theorem 4. There is an ODC of Kn,n by G if there exists a symmetric base that is isomorphic to the graph G. In the next section we use the symmetric base in constructing an ODC of Kn,n by different classes of graphs. Definition 6. Let r ≥ 1, and n1, n2, n3, · · · , nr be positive integers such that ni ≥ 0 for i ∈ {1, 3, · · · , r}.The caterpillar tree Cr(n1, n2, n3, · · · , nr) is the tree obtained from the path Pr = x1x2x3 · · ·xr by joining vertex xi to ni new vertices, i ∈ {1, 2, · · · , r}. Definition 7. Let δ, α be positive integers and the parameter xδ, ≥ 0. The rooted tree τα(x1, x2, x3, · · · , xδ) is the tree with a root α (α ∈ V (Kn,n)) and for all i ∈ {1, 2, · · · , δ} , xi is the number of leaves of level i. Figure 2: Tree τ00(1, 3) as a subgraph of K4,4. For example, the graph in Figure 2, represents a tree τα(x1, x2) ≊ τ00(1, 3) as a subgraph of K4,4. Such tree τ00(1, 3) is a rooted tree with a root α = 00, x1 = 1 (one leaf in level 1), while x2 = 3 (3 leaves with level 2). Remark 2. A Path Pr is caterpillar tree Cr(0, 0, 0, · · · , 0←−−−−−−−→ r ) H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3497 3. Designing orthogonal decompositions of Kn,n by certain trees In this section, we claim to construct ODC of Kn,n by certain trees based on BGA approach introduced in Section 2. 3.1. Orthogonal decompositions of Kn,n by rooted trees Theorem 5. Let n ≥ 3 be a positive integer and x1 ∈ {1, 2}, then there is a symmetric base of an ODC of Kn,n by G ≊ τ01(x1, ⌊ n−1 2 ⌋ ). Proof. case 1. Let x1 = 1, m ∈ Z+ and n = 2m+1. Then the vector v(G) of the base G, is defined as vi(G) = { i if 0 ≤ i ≤ m −i if m+ 1 ≤ i ≤ 2m Therefore, v−i(G) = { i if 0 ≤ i ≤ m −i if m+ 1 ≤ i ≤ 2m For all i ∈ Z2m+1, vi−v−i+ i = i. By Theorem 3, G is a symmetric base. By definition of v(G), the graph G ≊ τ01(1,m). E(G) = {(00, 01)} ∪ {(i0, 01) : 1 ≤ i ≤ m} ∪ {(i0, (2i)1 : 1 ≤ i ≤ m)} Case 2. Let x1 = 2, m ∈ Z+ and n = 2m, then the vector v(G) of the base G is defined as: vi(G) = v−i(G) = { i if 0 ≤ i ≤ m −i if m+ 1 ≤ i ≤ 2m− 1 For i ∈ Z2m, vi − v−i + i = i. By Theorem 3, G is a symmetric base. By definition of v(G), for any i ∈ Z2m, the graph G ≊ τ01(2,m− 1). E(G) = {(00, 01)} ∪ {(i0, 01) : 1 ≤ i ≤ m} ∪ {(i0, (2i)1 : 1 ≤ i ≤ m− 1)} Example 1. There is an ODC of K5,5 by τ01(1, 2), since v(G) = (0, 1, 2, 2, 1) is a sym- metric base, see Figure 3. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3498 Figure 3: Symmetric base of an ODC of K5,5 by τ01(1, 2). Theorem 6. Let n ≥ 5 be a positive integer, then there is an ODC of Kn,n by τ00(n−4, 2) Proof. For any positive integer n ≥ 5, the vectors v(G) and u(F ) of the bases G and F are represented as : vi(G) =  (n− 2)i if i = 0, n− 2 −2i− 1 if i = 1, n− 1 −i otherwise ui(F ) =  (n− 1)i if i = 0, n− 2 −i− 1 if i = 1, n− 1 0 otherwise From the representation of v(G) and u(F ), vi(G)−ui(F ) = 0 at i = 0, vi(G)−ui(F ) = 2 at i = n− 2, and vi(G)− ui(F ) = −i otherwise. Consequently, {vi(G)− ui(F ); i ∈ Zn} = Zn. By theorem 4, the two bases v(G) and u(F ) are orthogonal. Moreover, the edges set E(G) and E(F ) of the bases G and F respectively can be represented by: E(G) = {(((n− 2)i)0 , ((n− 1)i)1 ; i = 0, n− 2} ∪{((−2i− 1)0 , (−i− 1)1) ; i = 1, n− 1} ∪{(−i0, 01); i ∈ Zn\ {0, 1, n− 2, n− 1}} and E(F ) = {(((n− 1)i)0 , 01); i = 0, n− 2} ∪{((−i− 1)0 , (n− 1)1); i = 1, n− 1} ∪{(00, i); i ∈ Zn\ {0, 1, n− 2, n− 1}} Therefore, G ∼= F ∼= τ00(n− 4, 2). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3499 Theorem 7. Let n > 3 to be an odd integer and x1, x2 and γ ∈ Zn. Then there is a symmetric base of an ODC of Kn,n by G ≊ τ00(x1, x2) ∪ γK2. Proof. Case 1. Let m,n be positive integers such that n = 2m + 1, n > 3 and n ≇ 0mod 3. The vector v(G) of the base G is defined as: vi(G) = { 2i if 0 ≤ i ≤ m 0 if m+ 1 ≤ i ≤ 2m Hence, v−i(G) = { 0 if 0 ≤ i ≤ m −2i if m+ 1 ≤ i ≤ 2m For i ∈ Z2m+1, vi − v−i + i = 3i,since gcd(3, 2m + 1) = 1, By Theorem 3, G is a symmetric base. By definition of v(G), the graph G ≊ τ00(⌈n+1 3 ⌉, ⌈ n−3 6 ⌉) ∪ ⌊ n−1 3 ⌋K2, where x1 = ⌈n+1 3 ⌉, x2 = ⌈ n−3 6 ⌉ and γ = ⌊n−1 3 ⌋. Case 2. For an odd integer n > 3, n ≡ 0mod 3, the vector v(G) of the base G is represented as : vi(G)= { 2i if 0 ≤ i ≤ n−1 2 0 if n+1 2 ≤ i ≤ n− 1 Hence, v−i(G)= { 0 if 0 ≤ i ≤ n−1 2 −2i if n+1 2 ≤ i ≤ n− 1 For i ∈ Zn, vi−v−i+i = 3i. By Theorem 3, G is a symmetric base. By the definition of v(G), the graph G ≊ τ00(n3 , ⌊ n+1 5 ⌋)∪ ⌊ n−4 5 ⌋K2, where x1 = n 3 , x2 = ⌊ n+1 5 ⌋ and γ = ⌊n−4 5 ⌋. Theorem 8. Let n > 3,and n ≇ 0mod 3 be an even integer, then there is an ODC of Kn,n by G ≊ τ00(⌈n+2 3 ⌉, ⌈ n−3 6 ⌉) ∪ ⌊ n−2 3 ⌋K2. Proof. For any even integer n = 2m, m ∈ Z+, the vector v(G) of the base G is defined as : vi(G) = { 2i if 0 ≤ i ≤ ⌈n−1 2 ⌉ 0 if ⌈n+1 2 ⌉ ≤ i ≤ n− 1 Hence, v−i(G) = { 0 if 0 ≤ i ≤ ⌈n−1 2 ⌉ −2i if ⌈n+1 2 ⌉ ≤ i ≤ n− 1 For i ∈ Z2m, vi− v−i + i = 3i. Since gcd(3, 2m) = 1, By Theorem 3, G is a symmetric base. Moreover, the edges set E(G) of the basis G can be represented by: E(G)= { ((2i)0 , (3i)1) : 0 ≤ i ≤ ⌈n− 1 2 ⌉ } ∪ {(00, i1) : ⌈ n+ 1 2 ⌉ ≤ i ≤ n− 1}. By the definition of v(G), the graph G ≊ τ00(⌈n+2 3 ⌉, ⌈ n−3 6 ⌉) ∪ ⌊ n−2 3 ⌋K2. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3500 Theorem 9. Let m > 2, m ≇ 0mod 3, and m+ 3 to be an odd integer. Then there is a symmetric base of an ODC of Km+3,m+3 by G ∼= τ01(1, 2) ∪ (n− 5)K2. Proof. For all odd integer n > 5, n = m+ 3 such that m > 2, m ≇ 0mod 3, the vector v(G) of the symmetric base G can be defined as: vi(G) =  0 if i = 0 n− 1 if i = 1 3 if i = n− 1 xj − i if i ∈ {2, 3, · · · ,m+ 1} , j = i− 2 , Where xj = 1−j, for j ∈ {0, 1, 2, · · · ,m− 1} . From the definition of v(G), we find that vi−v−i+i = 0, for i = 0, for i = 1, vi−v−i+i = n−3, for i = n−1, vi−v−i+i = 3, and for i = j+2, j ∈ {0, 1, 2, · · · ,m− 1} , vi− v−i+ i = xj −xm−(j+1)− i. By Theorem 3, the base v(G) is symmetric. Moreover, the edges set E(G) of the base G can be represented by: E(G) = {(00, 01), ((n− 1)0 , 01), (30, 21)} ∪ { ( (xj − i)0 , (xj)1 ) } for all i = j + 2, j ∈ {0, 1, 2, · · · ,m− 1} . Then the graph G ∼= τ01(1, 2) ∪ (n− 5)K2. Theorem 10. Let n ≥ 3 to be a positive integer, then there is a symmetric base of an ODC of Kn,n by C4(0, 0, 0, 0) ∪ τ (n−1)1(n− 3). Proof. For a positive integer n ≥ 3, the vector v(G) of the base G can be written as: vi(G) =  0 if i = 0 n− 1 if i = 1, n− 1 −i− 1 otherwise , therefore, v−i(G) =  0 if i = 0 n− 1 if i = 1, n− 1 i− 1 otherwise , For i ∈ {0, 1, n− 1}, vi− v−i + i = i. For any i ∈ Zn\ {0, 1, n− 1} , vi− v−i + i = −i. Consequently, {vi − v−i + i; i ∈ Zn} = Zn. By Theorem 3, the base v(G) is symmetric. Moreover the edges set E(G) of the base G can be represented by: E(G) = {(00, 01) , (01, (n− 1)0) , ((n− 1)0, (n− 2)1)} ∪{(β0, (n− 1)1) : 1 ≤ β ≤ n− 3} . Then the graph G ∼= C4(0, 0, 0, 0) ∪ τ (n−1)1(n− 3). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3501 3.2. ODCs of Kn,n by a combination of caterpillar trees Theorem 11. Let α, β and γ be elements of Zn. For all positive integers n ≥ 7, and n ≇ 0mod 3, there is a symmetric base of an ODC of Kn,n by αC4(0, 0, 0, 0)∪βC3(0, 0, 0)∪ γC2(0, 0). Proof. Case 1. For an even integer n, let α = 2, β = n−8 2 , and γ = 2. The vector v(G) of a base G can be defined as: vi(G) = { −2i− 1 if i = 1, n− 1 −2i otherwise , Hence, v−i(G) = { 2i− 1 if i = 1, n− 1 2i otherwise For any i ∈ Zn, vi− v−i + i = −3i. By Theorem 3, the base v(G) is symmetric. Moreover, the edges set E(G) of the base G can be represented by: E(G) = {10, 01, 00, (n2 )1, 10} ∪ {(n− 3)0, (n− 2)1, ( n 2 )0, (⌊ n−3 2 ⌋)1} ∪{(2, n+2 2 ), (n− 2, n−2 2 )} ∪ {(n+4 2 )1, 40, 21} ∪ {(n+6 2 )1, 60, 31} ∪{(n+8 2 )1, 80, 41}∪, ...,∪{(n− 3)1, (n− 6)0, ( n−6 2 )1} then the graph G ≊ 2C4(0, 0, 0, 0) ∪ (p− 8)C3(0, 0, 0) ∪ 2C2(0, 0). Case 2. For an n odd integer n, let α = 1, β = 1, and γ = n− 5. The vector v(G) of a base G can be defined as: vi(G) = { −2i− 1 if i = 1, n− 1 −2i otherwise Hence, v−i(G) = { 2i− 1 if i = 1, n− 1 2i otherwise For any i ∈ Zn, vi− v−i + i = −3i. By Theorem 3, the base v(G) is symmetric. Moreover the edges set E(G) of the base G can be represented by: E(G) = {(−2i− 1)0 , (−i− 1)1 ; i ∈ {1, n− 1}} ∪ {(−2i)0 , (−i)1 ; i ∈ Zn \ {1, n− 1}} then the graph G ≊ C4(0, 0, 0, 0) ∪ C3(0, 0, 0) ∪ (n− 5)C2(0, 0). Theorem 12. Let p ≥ 13 to be a prime integer, then there an ODC of Kp,p by G = C4(0, 0, 0, 0) ∪ C3(0, 0, 0) ∪ (p− 5)C2(0, 0). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3502 Proof. For any prime integer p ≥ 13, the vectors v(G) and u(F ) of the bases G and F are: vi(G) =  (p−5 2 )i if i = 0, 1 (p−3 2 )i if 2 ≤ i ≤ p− 3 (p−5 2 )i− 2 if i = p− 2, p− 1 , and ui(F ) =  ( ⌈p−2 2 ⌉)i if i = 0, 1 (⌈p2⌉)i if 2 ≤ i ≤ p− 3 ⌈p−2 2 ⌉)i− 2 if i = p− 2, p− 1 , Hence, vi(G)−ui(F ) = (p−5 2 )i− ( ⌈p−2 2 ⌉ ) i if i ∈ {0, 1} , vi(G)−ui(F ) = (p−3 2 )i− ( ⌈p2⌉ ) i if i ∈ {2, 3, · · · , p− 3} , and vi(G) − ui(F ) = (p−5 2 )i − ⌈p−2 2 ⌉)i if i ∈ {p− 2, p− 1} . By theorem 4, then the two bases v(G) and u(F ) are orthogonal. Moreover, the edges set E(G) and E(F ) of the bases G and F respectively can be represented by: E(G) = {(( (p−5 2 )i ) 0 , ( (p−3 2 )i ) 1 ) ; i ∈ {0, 1} } ∪ {(( (p−3 2 )i ) 0 , ( (p−1 2 )i ) 1 ) ; i ∈ {2, 3, · · · , p− 3} } ∪ {(( (p−5 2 )i− 2 ) 0 , ( (p−3 2 )i− 2 ) 1 ) ; i ∈ {p− 2, p− 1} } . And E(F ) = {(( ⌈p−3 2 ⌉i ) 0 , ( ⌈p−1 2 ⌉i ) 1 ) ; i ∈ {0, 1} } ∪ {(( ⌈p−5 2 ⌉i ) 0 , ( ⌈p−3 2 ⌉i ) 1 ) ; i ∈ {2, 3, · · · , p− 3} } ∪ {((( ⌈p−3 2 ⌉i ) − 2 ) 0 , (( ⌈p−1 2 ⌉i ) − 2 ) 1 ) ; i ∈ {p− 2, p− 1} } . Hence G ≊ F ≊ C4(0, 0, 0, 0) ∪ C3(0, 0, 0) ∪ (p− 5)C2(0, 0). Theorem 13. Let n ≥ 8 to be a positive integer, then there is an ODC of Kn,n by C5(0, 0, (n− 4), 0, 0). Proof. For all positive integers n ≥ 8, the vectors v(G) and v(F ) of the bases G and H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3503 F are defined as: vi(G) =  −3i if i = 0, 1 −i if 2 ≤ i ≤ n− 3 −2− 3i if i = n− 2, n− 1 and vi(F ) =  −2i if i = 0, 1 0 if 2 ≤ i ≤ n− 3 −2i− 2 if i = n− 2, n− 1 Since {vi(G)− vi(F ); i ∈ Zn} = Zn, following Theorem 4, the bases G and F are orthogonal. From the above definitions of vi(G) and vi(F ) with the two relations E(G) = {(vi(G))0 , (vi(G) + i)i} and E(F ) = {(vi(F ))0 , (vi(F ) + i)i} for all i ∈ Zn, then G ≊ C5(0, 0, (n− 4), 0, 0) ≊ F . Theorem 14. Let n to be a positive integer such that n ≥ 5, then there is a symmetric base of an ODC of Kn,n by G = C3(1, 0, n− 3). Proof. For n ≥ 5, the vector v(G) of the base G can be defined by: vi(G) = v−i(G) = { n− 1 if i = 1, n− 1 1 otherwise For any i ∈ Zn, vi− v−i+i = i. By Theorem 3, the base v(G) is a symmetric. Moreover, the edges set E(G) of the base G can be represented by: E(G) = {01, (n− 1)0, (n− 2)1} ∪10 {(10, β1) : β ∈ {1, 3, · · · , n− 1}} Thus, the graph G ∼= C3(1, 0, n− 3). Theorem 15. Let p ≥ 5 to be prime integer, then there is a symmetric base of an ODC of Kp,p by C5(0, 0, 0, 0, 0) ∪ (p− 4)C2(0, 0). Proof. For a prime integer p ≥ 5, the vector v(G) of the base G is defined as: vi(G) = { i− 1 if i = 1, p− 1 3 + i otherwise hence, v−i(G) = { −i− 1 if i = 1, p− 1 3− i otherwise For any i ∈ Zp, vi−v−i+ i = 3i, Since gcd(3, p) = 1, By Theorem 3, G is a symmetric base. By the definition of v(G), the base G ∼= C5(0, 0, 0, 0, 0) ∪ (p− 4)C2(0, 0). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3504 Theorem 16. Let p ≥ 5 to be prime integer such that p = 5 + 6n, and n be a non negative integer, such that n ̸= 0mod 5, then there is a symmetric base of an ODC of Kp,p by C3(0, 0, 0) ∪ Cp−1(0, 0, · · · , 0︸ ︷︷ ︸ p−1 times ). Proof. For all prime integers p ≥ 5, p = 5 + 6n, and a non negative integer n ̸= 0mod 5.The vector v(G) of the base G can be defined as: vi(G) = { 0 if i = 0 i2 + i+ 1 otherwise , hence, v−i(G) = { 0 if i = 0 i2 − i+ 1 otherwise From the definition of vi(G) and v−i(G), {vi − v−i + i; i ∈ Zp }=Zp. By Theorem 3, the base v(G) is symmetric. Moreover, the edges set E(G) of the base G can be represented by: E(G) = {(00, 01) , (10, 01) } ∪ { ( (i2 + i+ 1)0, ( (i+ 1)2 ) 1 ) ; 1 ≤ i ≤ p− 2} thus the graph G ∼= C3(0, 0, 0) ∪ Cp−1(0, 0, · · · , 0︸ ︷︷ ︸ p−1 times ). Theorem 17. Let m ≥ 2, then there is a symmetric base of an ODC of Km+3,m+3 by G ∼= C4(0, 0, 1,m− 1). Proof. For a positive integer m ≥ 2,the vector v(G) of the base G in Km+3,m+3 can be defined as: vi(G) =  0 if i = 0, 1 2 if i = m+ 2 xj if i ∈ {2, 3, · · · ,m+ 1} , j = i− 2 , Where xj = 1− j, for j ∈ {0, 1, 2, · · · ,m− 1} . Moreover, vi − v−i + i =  0 if i = 0 − i if i ∈ {1,m+ 2} xj − xm−(j+1) + i if i = j + 2; j ∈ {0, 1, 2, · · · ,m− 1} . Hence, {vi − v−i + i; i ∈ Zm+3} = Zm+3. By Theorem 3, the base v(G) is symmetric. Moreover, the edges set E(G) of the base G can be represented by: H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3505 E(G) = {(00, 01), (10, 31)} ∪ (20, 11) , (11, 00) , (00, 31)} ∪{((31, (3− i)0) : 4 ≤ i ≤ m+ 1} That yields G ∼= C4(0, 0, 1,m− 1). Theorem 18. Let p to be a prime integer s.t p ≥ 13, and m = n− 3. Then there is an ODC of Kp,p by C4(0, 0, 0, 0) ∪ 2C3(0, 0, 0) ∪ (p− 7)C2(0, 0, ). Proof. For a prime integer p ≥ 13, the vectors v(G) and u(F ) of the bases G and F are defined as : vi(G) =  i if i = 0, p− 1 3 if i = 1 xj + 3i if i = j + 2, j ∈ {0, 1, 2, · · · ,m− 1} , and ui(F ) =  0 if i = 0 (n− 2) if i = 1 2− 2i if i = p− 1 xj − 2i if i = j + 2, j ∈ {0, 1, 2, · · · ,m− 1} , For all i ∈ Zp, vi(G) − ui(F ) = 5i. By theorem 4, then the two bases v(G) and u(F ) are orthogonal. Moreover the edges set E(G) and E(F ) of the bases G and F respectively can be represented by: E(G) = {(00, 01), ((p− 1)0 , (p− 2)1), (30, 41)} ∪{ ( (xj + 3i)0 , (xj + 4i)1 ) ; i = j + 2, j ∈ {0, 1, 2, · · · ,m− 1}} and E(F ) = {(00, 01), ((p− 2)0 , (p− 1)1), (40, 31)} ∪{ ( (xj − 2i)0 , (xj − i) ) ; i = j + 2, j ∈ {0, 1, 2, · · · ,m− 1}} which yields G ∼= F ∼= C4(0, 0, 0, 0) ∪ 2C3(0, 0, 0) ∪ (p− 7)C2(0, 0, ). Theorem 19. Let p ≥ 7 to be a prime integer, then there is an ODC of Kn,n by 2C3(0, 0, 0) ∪ (p− 4)C2(0, 0). Proof. For any prime integer p ≥ 7, α1 = ⌊3p−7 10 ⌋, α2 = ⌊2p3 ⌋ − 1, the vectors v(G) , v(M) and v(F ) of the starters G,M and F are defined as: Case 1. let p be a prime integer such that p ≡ 1mod 6 and α1be a positive integer α1 = ⌊3p−7 10 ⌋. The vectors v(G) , u(M) of the bases G and M are defined as: H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3506 vi(G) =  0 if i = 0, p− 2 p− 1 if i = 1, p− 1 i otherwise and ui(M) =  α1i if i = 0, p− 2 α1i− 1 if i = 1, p− 1 (α1 + 1)i otherwise Therefore, vi(G)−ui(M) = −α1i for any i ∈ Zp. Consequently, {vi(G)−ui(M)} = Zp. By theorem 4, then the two bases v(G) and u(M) are orthogonal. Moreover, the edges set E(G) and E(M) of the bases G and M respectively, can be represented by: E(G) = {(00, 01), (00,−21)} ∪{((p− 1)0 , (i− 1)1); i = 1, p− 1} ∪{(i0, 2i1); i ∈ Zn\ {0, 1, p− 2, p− 1}} E(M) = {((α1i)0 , ((α1 + 1)i)1) ; i = 0, p− 2} ∪{((α1i− 1)0 , (((α1 + 1)i)− 1)1); i = 1, p− 1} ∪{(((α1 + 1)i)0 , ((α1 + 2)i)1) ; i ∈ Zn\ {0, 1, p− 2, p− 1}} and hence G ∼= M ∼= 2C3(0, 0, 0) ∪ (p− 4)C2(0, 0). Case 2. let p to be a prime integer such that p ≡ 5mod 6 and α2 be a positive integer α2 = ⌊2p3 ⌋ − 1. The vectors v(G) , h(F ) of the bases G and F are defined as: vi(G) =  0 if i = 0, p− 2 p− 1 if i = 1, p− 1 i otherwise and hi(F ) =  α2i if i = 0, p− 2 α2i− 1 if i = 1, p− 1 (α2 + 1)i otherwise Therefore, vi(G)−hi(F ) = −α2i for any i ∈ Zp. Consequently, {vi(G)−hi(F )} = Zp. By theorem 4, then the two bases v(G) and h(F ) are orthogonal. Moreover, the edges set E(F ) of the basis F can be represented by: E(F ) = {((α2i)0 , ((α2 + 1)i)1) ; i = 0, p− 2} ∪{((α2i− 1)0 , (((α2 + 1)i)− 1)1); i = 1, p− 1} ∪{(((α2 + 1)i)0 , ((α2 + 2)i)1) ; i ∈ Zn\ {0, 1, p− 2, p− 1}} and hence F ∼= 2C3(0, 0, 0) ∪ (p− 4)C2(0, 0). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3507 Theorem 20. Let p > 7 to be a prime integer, then there is an ODC of Kn,n by C3(1, p− 4, 1) ∪ (p− 5)C2(0, 0). Proof. Case 1. For any prime integer p > 7 such that p ≡ 5mod 6 and a positive integer α1 = ⌊p3⌋, the vectors v(G) and u(M) of the bases G and M are defined as: vi(G) =  0 if i = 0, p− 2 p− 1 if i = 1, p− 1 i otherwise and ui(M) =  α1i if i = 0, p− 2 α1i− 1 if i = 1, p− 1 (α1 + 1)i otherwise , Therefore, vi(G)− ui(M) = −α1i for every i ∈ Zp. Consequently, {vi(G)− ui(M)} = Zp. By theorem 4, then the two bases v(G) and u(M) are orthogonal. Moreover, the edges set E(G) and E(M) of the bases G and M respectively, can be represented by: E(G) = {((p− 1)0 , (i− 1)1); i = 1, p− 1} ∪{(00, 01), (00,−21)} ∪{(i0, 2i1); i ∈ Zn\ {0, 1, p− 2, p− 1}} and E(M) = {((α1i)0 , ((α1 + 1)i)1) ; i = 0, p− 2} ∪{((α1i− 1)0 , (((α1 + 1)i)− 1)1); i = 1, p− 1} ∪{(((α1 + 1)i)0 , ((α1 + 2)i)1) ; i ∈ Zn\ {0, 1, p− 2, p− 1}} and hence G ∼= M ∼= C3(1, p− 4, 1) ∪ (p− 5)C2(0, 0). Case 2. For any prime integer p > 7 such that p ≡ 1mod 6 and a positive integer α2 = ⌊3p−1 5 ⌋ , the vectors v(G) and h(F ) of the bases G and F are defined as: vi(G) =  0 if i = 0, p− 2 p− 1 if i = 1, p− 1 i otherwise and hi(F ) =  α2i if i = 0, p− 2 α2i− 1 if i = 1, p− 1 (α2 + 1)i otherwise Therefore, vi(G)−hi(F ) = −α2i for every i ∈ Zp. Consequently, {vi(G)−hi(F )} = Zp. By theorem 4, then the two bases v(G) and h(F ) are orthogonal. Moreover, the edges set E(F ) of the bases F can be represented by: H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3508 E(F ) = {((α2i)0 , ((α2 + 1)i)1) ; i = 0, p− 2} ∪{((α2i− 1)0 , (((α2 + 1)i)− 1)1); i = 1, p− 1} ∪{(((α2 + 1)i)0 , ((α2 + 2)i)1) ; i ∈ Zn\ {0, 1, p− 2, p− 1}}. and hence F ∼= C3(1, p− 4, 1) ∪ (p− 5)C2(0, 0). Theorem 21. Let p > 7 to be a prime integer, then there is an ODC of Kp,p by C4(0, 0, 0, 0) ∪ 2C3(0, 0, 0) ∪ (p− 7)C2(0, 0). Proof. For any prime integer p > 7, the vectors v(G) and u(F ) of the starters G and F are defined respectively as: vi(G) =  0 if i = 0 (p−1 2 )i− 1 if i = 1, p− 1 (p−3 2 )i− 1 otherwise and ui(F ) =  0 if i = 0 (p+1 2 )i− 1 if i = 1, p− 1 (p−1 2 )i− 1 otherwise Thus, for any i ∈ Zp, vi(G)− ui(F ) = −i. Consequently, {vi(G)− ui(F ); i ∈ Zp} = Zp. By theorem 4, then the two bases v(G) and u(F ) are orthogonal. Moreover, the edges set E(G) and E(F ) of the bases G and F respectively, can be represented by: E(G) = {(( (p−1 2 )i− 1 ) 0 , ( (p+1 2 )i− 1) ) 1 ) ; i ∈ {1, p− 1} } ∪{(00, 01)} ∪ {(( (p−3 2 )i− 1 ) 0 , ( (p−1 2 )i− 1) ) 1 ) ; i ∈ Zp\ {0, 1, p− 1} } and E(F ) = {(( (p+1 2 )i− 1 ) 0 , ( (p+3 2 )i− 1) ) 1 ) ; i ∈ {1, p− 1} } ∪{(00, 01)} ∪ {(( (p−1 2 )i− 1 ) 0 , ( (p+1 2 )i− 1) ) 1 ) ; i ∈ Zp\ {0, 1, p− 1} } . Hence, G ∼= F ∼= C4(0, 0, 0, 0) ∪ 2C3(0, 0, 0) ∪ (p− 7)C2(0, 0). H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3509 4. Tree- binary error detecting and correcting codes Various combinatorial designs and related structures can be utilized to create codes using the incidence matrix. The interaction between designs and codes has led to many intriguing and valuable results [12] as a good survey. Lately, there has been a heightened focus on codes derived from graphs. The literature extensively delves into the relationship between codes and graphs from multiple perspectives. The primary aim of these studies is to select a specific class of graphs and form codes from the graph’s adjacency matrix. The characteristics of the graph can give rise to diverse types of codes, including self-dual codes, self-orthogonal codes, authentication codes, etc. Further details on this subject can be found in [2, 4, 5, 8, 9, 13, 15, 17–19]. Binary codes can be produced from various graphs such as Paley graphs and Latin square graphs [3, 23]. Furthermore, non-isomorphic codes have been generated from non-isomorphic graphs. This section focuses on binary codes originating from the row span of the incidence matrices of particular graphs that appear as induced subgraphs of complete bipartite graphs. These codes are termed binary graph-codes. Additionally, if each codeword in a graph-code corresponds to a graph that is isomorphic to graph G, the code is known as a binary G−code. By utilizing an ODC of a complete bipartite graph, we develop binary codes that ensure the inner product of any two codewords is less than or equal to 1. Therefore, binary G−codes are viewed as a distinct subset of orthogonal codes. The unique properties of an ODC of a complete bipartite graph suggest that binary G−codes derived from ODCs may serve as effective error detection and correction codes. Theorem 22. Let there is an ODC of Kn,n by a tree. Then there is a tree- binary code of length n2. Proof. Given an ODC G ={Gi a : a ∈ Zn, i ∈ {1, 2}} of Kn,n by a tree G. The incidence matrix L = L (s, t) for such ODC G ={Gi a; a ∈ Zn, i ∈ {1, 2}} is a 2n× n2 binary matrix showing the relation between the edges of Kn,n and the the members of G such that every row in L corresponds to a unique graph in G and every column in L corresponds to a unique edge in Kn,n. Let the edge (α0, β1) ∈ E (Kn,n) . Then L has a unique column t corresponds to this edge (α0, β1). Such column t is defined from an injective function C : E (Kn,n)→{ 0, 1, · · · , n2 − 1 } where C ((α0, β1)) = t = nα + β; α, β ∈ Zn. For each a graph Gi a : (a ∈ Zn, i ∈ {1, 2}), a ∈ Zn from G, there is exactly one row s ∈ {0, 1, · · · , 2n− 1} in L corresponds to Gi a according the injective function RG : Zn × {1, 2} → {0, 1, · · · , 2n− 1} where RG (a, i) = s = { a if i = 1 a+ n if i = 2. Then, The incidence matrix L = L (s, t) of an ODC G is defined as L (s, t) = { 1 if (α0, β1) ∈ E ( Gi a ) 0 if (α0, β1) /∈ E ( Gi a ) H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3510 The rows of L can form a graph binary code. This binary code will be denoted as Cr. The encoding process in Cr is manipulated in two consecutive steps. Suppose that (a, i) ∈ Zn×{1, 2} is a plain text. . In order to build the cipher text for (a, i) , firstly, we calculate s = RG ( a, i) . using the above definition of RG. Secondly, the cipher text corresponds to the plain text ( a, i) is the concatenation of bits of the row s in the matrix Lso will be the codeword ls0ls1ls2···ls(n2−1) is the corresponding cipher text (of length n2 ) to the a plain text (a, i) . The definition of the matrix L = L (s, t) implies that every row in L is isomorphic to the tree G. Whence every codeword in Cr is also so. Thus, Cr is a tree binary code induced from an ODC of Kn,n by a tree G. The significance of the Hamming distance in binary codes lies in its ability to determine error detection and correction capabilities within the code. Consider a binary code C, where each codeword has a length of h. Let X = x1x2 · · ·xh and Y = y1y2 · · · yh be two codewords from C.The distance d (X,Y ) between X and Y is calculated as the count of differing bits between X and Y. Hence, d (X,Y ) = ∑h i=1 d (xi, yi) where, d (xi, yi) = 0 if xi = yi and d (xi, yi) = 1 if xi ̸= yi. The distance d (X,Y ) for any codewords X and Y in the binary code C follows specific properties: (i) d (X,Y ) ≥ 0. (ii) d (X,Y ) = 0 if and only if X = Y. (iii) d (Y,X) = d (X,Y ) . (iv) d (X,Z) ≤ d (X,Y ) + d (Y, Z) . The minimum distance d (C) of a code C is defined as d (C) = min {d (X,Y ) ; X,Y ∈ C and X ̸= Y } . Lemma 1. Let Cr be a tree binary codes constructed from the rows of the incidence matrix of an ODC of Kn,n by a tree. Then the minimum distance d (Cr) is 2n− 2. Proof. From the relation between ODC and the incidence matrix L, there exists n 1’s in every row. Any two rows have at most 1 position of 1’s common. Then the minimum distance of Cr is 2 (n− 1) = 2n− 2. Theorem 23. The binary code Cr can detect up to 2n − 3 errors or correct up to⌊ 2n−3 2 ⌋ errors. Proof. From Lemma 1, the minimum distance of Cr is 2 (n− 1) . Thus, in order to change any codeword to another codeword requires at least 2n− 2 bit changes. Whence, Cr can detect up to 2n−2−1 = 2n−3 errors, since any 2n−3 transmission errors cannot change one codeword to another. Hence, in order to have a guarantee the detection of up to k errors in all cases, the minimum distance of the code Cr, d (Cr) = k + 1. The Geometric concept for finding d (Cr) in error detection is shown in Figure 4. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3511 Suppose that the codeword u was sent but for some reason v was received and d (u, v) ≤ 2n−3 2 , that is less than 2n−3 2 errors occurred. Subsequently, the distance between v and any codeword, excluding u, exceeds 2n−3 2 . Let w ∈ Cr then d (u,w) ≥ 2n− 2. Therefore, if u is the closest codeword to v, the amount of bit changes needed to switch from u to v (the number of errors in the transmission channel) is lower than the number of errors needed to switch from any other codeword to v. The substitution of v with u enables Cr to rectify up to 2n errors. Therefore, to ensure the correction of k errors in all instances, the minimum distance of code Cr d (Cr) = 2k+1.The geometric principle for determining d (Cr) in error correction is presented in Figure 5. Figure 4: The Geometric concept for finding d (Cr) in error detection. Figure 5: The Geometric concept for finding d (Cr) in error correction. H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3512 Example 2. Let the vector (0, 1, 2, 1) be a symmetric base for an ODC of K4,4 by τ 01(2, 1). The two orthogonal decompositions generated from the vector (0, 1, 2, 1) are shown in Fig- ure 6.The incidence matrix L = L (s, t) for such ODC is a 8×16 binary matrix where the rows correspond to elements of ODC G ={Gi 0+x : x ∈ Z4, i ∈ {1, 2}} of K4,4.The following matrix is the incidence matrix L (s, t) for the ODC (described in Figure 6) of K4,4 by τ01(2, 1). From the rows of the matrix L (s, t) we construct the code Cr such that Cr has 8 codewords each of length 16. Figure 6: An ODC of K4,4 by τ01(2, 1) where the vector (0, 1, 2, 1) is the symmetric base for this ODC.  1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1  ←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ The incidence matrix L(s,t) for the ODC described in Figure 6 ↓ Cr =  1000101010000000, 0000010001010100, 001000000010100, 01010010000000, 1110000001000000, 0000011100000010, 0001000010110000, 0000100000001101  ←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ The code Cr deduced from the rows of the above incidence matrix L(s,t) H. Shabana, R. El-Shanawany, S. Halawa / Eur. J. Pure Appl. Math, 17 (4) (2024), 3492-3516 3513 5. Recursive construction of an ODC by disjoint trees Hereafter, we will show how to use an ODC of small complete bipartite graphs to construct an ODC of larger complete bipartite graphs. In the following, for simplicity, if (x, y) ∈ Zm × Zn, we use xy for (x, y) . Theorem 24. Let m ≡ 1mod 6 or m ≡ 5mod 6 and let n be a positive integer. If v(G) = (v0, v1, · · · , vn−1) be a symmetric base for an ODC of Kn,n by a certain tree G, then there is an ODC of Kmn,mn by mG with respect to Zn×Zm, (the Cartesian product of the groups Zn and Zm). Proof. Let the vector u(F ) = (u0, u1, · · · , um−1) = (0, 1, · · · ,m − 1) represent a base in Km,m with respect to Zm. From the definition of u(F ), We can conclude that {ui − u−i + i; i ∈ Zm} = Zm. Therefore, u(F ) is a symmetric base an ODC of Km,m. Whence, m ≡ 1mod 6 or m ≡ 5mod 6 the base F is isomorphic to mK2. Since the vector v(G) = (v0, v1, · · · , vn−1) is a symmetric base for an ODC of Kn,n. Taking the Cartesian product of the two vectors v(G) and u(F ) implies that v(G) × u(F ) = ((v0, u0) , (v0, u1) , · · · , (vi, uj) , · · · , (vn−1, um−1) ; i ∈ Zn, j ∈ Zm) is also a symmetric base of an ODC of Kmn,mn by G× F with respect to Zn × Zm, as {(vi, uj)− (v−i, u−j) + (i, j) ; i ∈ Zn, j ∈ Zm} = Zn × Zm,. Moreover,the edge set of the the base G× F is E(G× F ) = { (vi, uj)0 ,+((vi, uj) + (i, j))1 ; i ∈ Zn, j ∈ Zm } . From the vectors u(F ) and v(G) the baseG×F is isomorphic tomG wheneverm ≡ 1mod 6 or m ≡ 5mod 6 and n be a positive integer. Note that the the vertices of Kmn,mn are labelled by the elements of Zn ×Zm ×{0, 1}.For the vertex (x, y, i) we write (xy)0 where x ∈ Zn, y ∈ Zn, i ∈ {0, 1}, and Zn = {0, 1, 2, · · · , n−1} is the group of all residual classes modulo n, Zm = {0, 1, 2, · · · ,m− 1} is the group of all residual classes modulo m. Example 3. Given the vector v(F ) = (0, 1, 2, 3, 4) as a symmetric base for an ODC of K5,5 by 5K2. If there is an ODC of K3,3 by τ01(1, 1) where the vector v(G) = (0, 1, 1) is the symmetric base for this ODC then we have a guarantee that there is an ODC of K15,15 by 5τ01(1, 1) and the v(G)× u(F ) = (00, 01, 02, 03, 04, 10, 11, 12, 13, 14, 10, 11, 12, 13, 14) the base G× F is illustrated in Figure 7 REFERENCES 3514 Figure 7: Symmetric base for an ODC of K15,15 by 5τ01(1, 1). 6. Concluding Remarks The paper delves into the concept of graph decomposition, particularly focusing on orthogonal decompositions. In this context, a graph H is divided into subgraphs in such a way that any two subgraphs share at most one edge. These decompositions are re- ferred to as G−orthogonal decompositions if each subgraph is isomorphic to the graph G. The applications of such decompositions are widespread, encompassing fields like statis- tics, information theory, and experimental design theory. The document also introduces an approach for constructing orthogonal decompositions of regular graphs and discusses its utilization in creating tree-orthogonal decompositions of complete bipartite graphs. Additionally, the use of orthogonal decompositions in designing hamming tree-codes is explored, supported by examples showcasing their effectiveness in error detection and cor- rection during data transmission. In future wok, further investigations will be planed to manipulate our approach to work on irregular graphs. Declaration of Conflicting Interests The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article. Acknowledgements We are grateful to the reviewers for a number of valuable remarks and suggestions. References [1] R. Balakrishnan and K. Ranganathan. A Textbook of Graph Theory. Springer, Berlin, 2012. [2] O. G. El Barbary and Radwan Abu Gdairi. Neutrosophic logic-based document summarization. Journal of Mathematics, 2021(11):Article ID: 9938693, 2021. [3] C.J. Colbourn and J. H. Dinitz. Handbook of Combinatorial Designs, 2nd Ed. Chap- man and Hall-CRC, Berlin, 2007. REFERENCES 3515 [4] R. Abu-Gdairi, A. A. El Atik, M. K. El-Bably and M. A. El-Gayar. Topological visu- alization and graph analysis of rough sets via neighborhoods: A Medical application using human heart data. Aims Mathematics., 8(11):26945–26967, 2023. [5] H. Shabana, R. El-Shanawany and S. R. Halawa. Graph design for data authentication over insecure communication channel. Alexandria Engineering Journal, 75:649–662, 2023. [6] R Scapellato, R. El-Shanawany and M. Higazy. Orthogonal double covers of Cayley graphs. Discrete Appl Math., 157:3111–3118, 2009. [7] S. El-Serafi, R. El-Shanawany, and H. Shabana. Orthogonal double cover of complete bipartite graph by disjoint union of complete bipartite graphs. Ain Shams Eng. J., 6:657–660, 2015. [8] W. Fish, R. Fray and E. Mwambene. Binary codes from the complements of the triangular graphs. Quaestiones Mathematicae, 33:399–408, 2010. [9] M. Grassl and M. Harada. New self-dual additive F4-codes constructed from circulant graphs. Discrete Math., 340:399–403, 2017. [10] R. El-Shanawany, S. A. El-Sheikh, S. R. Halawa and H. Shabana. Graph Based Approach for Error-Detecting and Correcting Codes. Applied Mathematics and In- formation Sciences, 16:995–1003, 2022. [11] S. Hartmann and U. Schumacher. Orthogonal double covers of general graphs. Graphs Combin.Discrete Appl. Math., 138:107–116, 2004. [12] E. F. Assmus. Jr, J. D. Key. Designs and codes: An update. Des. Codes cryptogr., 9:7–27, 1996. [13] J. D. Key and B. G. Rodrigues. LCD codes from adjacency matrices of graphs. Appl. Alg. Eng. Comm. Comp., 29:227–244, 2018. [14] H.-D.O.F. Gronau, S. Hartmann, M. Grüttmüller, U. Leck and V. Leck. On orthog- onal double covers of graphs. Codes Cryptogr., 27:49–91, 2002. [15] D. Leemans and B. G. Rodrigues. Binary codes of some strongly regular subgraphs of the McLaughlin graph. Des. Codes Cryptogr., 67:93–109, 2013. [16] H.-D.O.F. Gronau, R.C. Mullin and A. Rosa. On orthogonal double covers of complete graphs by trees. Graphs Combin., 13:251–262, 1997. [17] W. H. Haemers, R. Peeters and J.M. Rijckevorsel. Binary codes of strongly regular Graphs. Des. Codes cryptogr., 17:187–209, 1999. [18] D. Crnkovic, M. Maximovic, B. Rodrigues and S. Rukavina. Self-orthogonal codes from the strongly regular graphs on up to 40 vertices. Adv. Math. Communications, 10:555–582, 2016. REFERENCES 3516 [19] D. Crnkovic, B. G. Rodrigues, S. Rukavina and L. Simcic. Ternary codes from the strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs. Discrete Math., 312:3000–3010, 2012. [20] R. Sampathkumar and S. Srinivasan. Cyclic orthogonal doubl covers of 4-regular circulant graphs. Discrete Mathematics, 311:2417–2422, 2011. [21] R. Sampathkumar and V. Sriram. Orthogonal σ−labeling of graphs. AKCE Inter- national Journal of Graphs and Combinatorics, 5(1):57–60, 2008. [22] M. Higazy, R. Scapellato and Y. S. Hamed. A complete classification of 5-regular circulant graphs that allow cyclic orthogonal double covers. Journal of Algebraic Combinatorics, 53:593–611, 2021. [23] V. D. Tonchev. Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs. IEEE Trans. Inform. Theory., 43:1021–1025, 1997.