EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 2, 2024, 1369-1384 ISSN 1307-5543 – ejpam.com Published by New York Business Global Vertex-Weighted (k1, k2) E-Torsion Graph of Quasi Self-Dual Codes Jupiter G. Pilongo1, Leonard M. Paleta1,∗, Philip Lester P. Benjamin1 1 Department of Mathematics and Statistics, College of Science and Mathematics, University of Southern Mindanao, 9407 Kabacan, North Cotabato, Philippines Abstract. In this paper, we have introduced a graph GEC generated by type-(k1, k2) E-codes which is (k1, k2) E-torsion graph. The binary codewords of the torsion code of C are the set of vertices, and the edges are defined using the construction of E-codes. Moreover, we characterized the graph obtained when k1 = 0 and k2 = 0 and calculated the degrees of every vertex and the number of edges of GEC . Moreover, we presented necessary and sufficient conditions for a vertex to be in the center of a graph given the property of the codeword corresponding to the vertex. Finally, we represent every quasi self-dual codes of short length by defining the vertex-weighted (k1, k2) E-torsion graph, where the weight of every vertex is the weight of the codeword corresponding to the vertex. 2020 Mathematics Subject Classifications: 05C25, 05C60, 05C62, 05C90, 11H71, 14G50 Key Words and Phrases: quasi-self dual codes, rings, torsion codes, E-codes, E-torsion graphs, graph representation, quasi-self dual codes 1. Introduction Linear codes, well-studied objects in coding theory, have traditionally been explored over fields or rings with unity. However, recent researches [2–4, 14] have unveiled a fasci- nating avenue of investigation by extending the study of linear codes to non-unital rings. For instance, Alahmadi, et al [1], introduced the notion of Quasi Self-Dual codes (QSD codes), self-orthogonal linear codes of length n over a non-unital ring E such that the size of the code is 2n. Moreover, there are some interesting researches in binary codes in the literature, for instance, [15] explored the Z2-triple cycle codes and their duals, [11] cyclic codes from a sequence over finite fields, and [6] studied self-dual codes over Rk and binary self-dual codes. In continuation to the codes over E, Shi, Minjia, et al. [14] presented a special construction of QSD codes over E, based on combinatorial matrices ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.4867 Email addresses: jgpilongo@usm.edu.ph (J. Pilongo), lmpaleta@usm.edu.ph (L. Paleta), plbenj@usm.edu.ph (P. Benjamin) https://www.ejpam.com 1369 © 2024 EJPAM All rights reserved. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1370 related to two-class association schemes, Strongly Regular Graphs (SRG), and Doubly Regular Tournaments (DRT). In this article, we delved into the analysis of graphs generated from linear codes over E, called linear E-codes and examine their properties and use these concepts to formulate a definition of graph. Graph theory provides a powerful framework for visualizing and understanding com- plex systems, making it an ideal tool for investigating linear codes over non-unital rings. By associating codes with corresponding graphs, we can gain insights into the structure and behavior of these codes, enabling us to extract valuable information related to er- ror correction, network coding, and other areas of interest. For standard notations and concepts in graph theory, the readers are advised to refer to [9]. In this study, we will first establish the foundations of linear codes over E, elucidating the necessary definitions, properties, and construction methods. Next, we will introduce the graph representation of such linear codes, by defining (k1, k2) E-torsion graph of an E-code, and will discuss the construction of such graphs and explore the relationship between the code’s properties and the resulting graph structure. Moreover, we will study vertex-weighted graph to separate the isomorphic graph generated by two inequivalent E-codes. The study of coding theory in relation to graph theory is not well-established topic. However, few researchers tried to focus on the subject such as graph theoretic methods in coding theory [13], where it discusses the application of graph theory in coding theory, and codes on graphs [8], where it developed a fundamental theory of realizations of linear and group codes on general graphs using elementary group theory, including basic group duality theory. Through our comprehensive analysis of graphs produced from linear codes over the non-unital ring E, this article seeks to contribute to the expanding field of coding the- ory and its applications in diverse domains. By exploring the interplay between graph theory and linear codes over non-unital rings, we strive to unlock new perspectives, in- sights, and practical solutions that can address challenges in error correction, information transmission, and beyond. 2. Background 2.1. Binary codes As defined in [14], denoted by wt(x) the Hamming weight of x ∈ Fn 2 . The dual of a binary code C is denoted by C⊥ and defined as C⊥ = {y ∈ Fn 2 |∀x ∈ C, (x, y) = 0, } where (x, y) = n∑ i=1 xiyi, J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1371 denotes the standard inner product. A code C is self-orthogonal if it is included in its dual: C ⊆ C⊥. Two binary codes are equivalent if there is a permutation of coordinates that maps one to the other. 2.2. Ring Theory We describe the main properties of the ring E of order four. The ring E is defined by the relations on two generators a, b and we shall write c = a+ b for the given ring. The ring E is defined by E = ⟨a, b|2a = 2b = 0, a2 = a, b2 = b, ab = a, ba = b⟩. It is a non-unital ring and non-commutative ring with characteristic two. For more details refer to [3, 7, 12]. The ring is local with maximal ideal {0, c}. Its multiplication table is given in Table 1. × 0 a b c 0 0 0 0 0 a 0 a 0 0 b 0 b b 0 c 0 c c 0 Table 1: Multiplication table for the ring E From Table 1, it is clear E is not commutative, and non-unital. It is local with the maximal ideal J = {0, c}, and residue field E/J = F = {0, 1}, the finite filed of order 2. If we denote α : E → E/J = F2, the map of reduction modulo J . It follows that α(0) = α(c) = 0, and α(a) = α(b) = 1. This function α is extended in the natural way in a map from En to Fn 2 . Readers who wanted further details on the properties of ring R, we refer the readers to [1–3, 10]. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1372 2.3. Codes over E A linear E-code of length n is a one-sided E-submodule of En. Let C be a code of length n over E. With the code, there are two binary codes of length n: (i) the residue code defined by res(C) = {α(y)|y ∈ C}, (ii) the torsion code defined by tor(C) = {x ∈ Fn 2 |cx ∈ C}. The right dual C⊥R of C is the right module defined by C⊥R = {y ∈ En|∀x ∈ C, (x, y) = 0}. The left dual C⊥R of C is the left module defined by C⊥L = {y ∈ En|∀x ∈ C, (y, x) = 0}. An E-code C is self-orthogonal if ∀x, y ∈ C, (x, y) = 0. It follows that C is self-orthogonal if and only if C ⊆ C⊥L . Similarly, C is self-orthogonal if and only if C ⊆ C⊥R . Hence, for a self-orthogonal code C, it satisfies that C ⊆ C⊥L ∩ C⊥R . An E−code of length n is Quasi Self-Dual (QSD for short) [14] if it is self-orthogonal and of size 2n. A quasi-self dual code is Type IV if all its codewords have even weight [5]. 3. Some results in linear E-codes 3.1. Linear E-codes Definition 1. [3] Let C be a linear E-code. Then C is a type-(k1, k2) code if dim(res(C)) = k1 and dim(tor(C)) = k1 + k2. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1373 Theorem 1. [3] Let B be a self-orthogonal binary code of length n. The code C defined by the relation C = aB + cB⊥, is a quasi self-dual code. Its residue code is B and its torsion code is B⊥. Corollary 1. [3] Let B and B′ be a binary code of length n such that B is self-orthogonal and B ⊆ B′. Then C is a linear E-code defined by the relation C = aB + cB′. 4. Results in (k1, k2) E-torsion graph of an E-code Definition 2. Let C be a linear E-code and B′ be the torsion code of C. Then the simple graph GEC such that the vertex set V (GEC) = B′ and xy ∈ E(GEC), the edge set and x ̸= y, if ax+ cy ∈ C or ay + cx ∈ C, is called the (k1, k2) E-torsion graph of C. To avoid the confusion to whether the binary code is viewed as a codeword in tor(C) or vertex in GEC , we denote the vertex x̂ which corresponds to the codeword x. This means that if x ∈ tor(C), then x̂ ∈ V (GEC). Example 1. Let C = aB + cB′ where B = ⟨1100⟩ and B′ = ⟨1100, 0011⟩ . This means that V (GEC) = {0̂000, 1̂100, 0̂011, 1̂111}. By computation, we get E(GEC) = {(0̂000, 1̂100), (0̂000, 0̂011), (0̂000, 1̂111), (1̂100, 0̂011), (1̂100, 1̂111)}. Thus, the (k1, k2)-torsion graph of C, GEC , is illustrated in Figure 1. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1374 Figure 1: (k1, k2) E-torsion graph of C Theorem 2. If C is a type-(k1, k2) of an E-code, then |V (GEC)| = 2k1+k2 and |E(GEC)| = 2k1∑ i=1 2k1+k2 − i. Proof. The equation |V (GEC)| = 2k1+k2 follows from the fact that the torsion of a type-(k1, k2) E-code has dimension k1 + k2. On the other hand, from the definition of E(GEC), E(GEC) = {(x̂, ŷ) : x ∈ res(C), y ∈ tor(C)}, that is, each of the 2k1 elements of the residue will be connected by an edge to the 2k1+k2 − 1 elements of the torsion. We can enumerate the edges by starting at an element in the residue with 2k1+k2 − 1 edges containing that element, then if there is another element of the residue, we will enumerate the 2k1+k2 − 2 edges containing the second element, since there is one edge common to the set of edges containing the first element and set of edges containing the second element, hence the second set of edges is 1 less than the previous set of edges. We continue the process by subtracting 1 from the number of the previous set of edges. Using this algorithm, the number of distinct pairs would be 2k1∑ i=1 2k1+k2 − i. ■ J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1375 Corollary 2. Let x̂ ∈ V (GEC). If x ∈ res(C), then deg(x̂) = 2k1+k2 − 1. If x /∈ res(C), then deg(x̂) = 2k1 . Proof. The proof follows from Theorem 2. ■ Corollary 3. If C is a type-(k1, k2) E-code, then |E(GEC)| = 22k1+k2 − 22k1−1 − 2k1−1. Proof. The proof follows directly from Corollary 2. ■ Lemma 1. r(GEC) = 1. Proof. If x ∈ res(C), then the eccentricity of x̂ is 1 since x̂ is connected by an edge to every vertex in GEC . If x /∈ res(C), then the eccentricity of x̂ is 2 since every vertex in GEC is connected through a vertex in res(C) to all other vertex not in res(C). Therefore, r(GEC) = 1. ■ Lemma 2. Let GEC ̸= P2, path of order 2. If there exists x /∈ res(C), then there exists y ̸= x such that y /∈ res(C). Proof. Let x /∈ res(C). Then |res(C)| < |tor(C)| . This means k1 < k1 + k2, that is, k2 > 0. Now, |tor(C)| − |res(C)| = 2k1+k2 − 2k1 = 2k1 ( 2k2 − 1 ) . Note that if k1 = 0 and k2 = 1, GEC ̸= P2, which is a contradiction. Thus, 2k1 ( 2k2 − 1 ) ≥ 2. ■ Theorem 3. Let C be an E-code and GEC be the (k1, k2) E-torsion graph of C which is not P2. Then vertex x̂ ∈ C(GEC) if and only if x ∈ res(C). J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1376 Proof. Let x̂ ∈ C(GEC). Suppose x /∈ res(C). Then, by Lemma 2 there exists y ∈ tor(C) such that both ax+ cy and ay + cx not in C. It follows that eccentricity of x̂ is greater than 1, a contradiction that x̂ ∈ C(GEC) by Lemma 1. Conversely, suppose x ∈ res(C). Then x̂ is connected by an edge to every vertex in GEC . Thus, the eccentricity of vertex x̂ is 1, that is, x̂ ∈ C(GEC). ■ 4.1. (k1, k2) E-torsion graph of QSD codes Quasi self-dual codes are classified in [3] using their residue codes. But since every residue code corresponds to a unique torsion code, the study of the structure of GEC of a QSD code will be concentrated in this section. Example 2. Let C = aB + cB⊥, where B = ⟨1100, 0011⟩ . Then B⊥ = ⟨1100, 0011⟩ By Theorem 1, C is a QSD code. V (GEC) = {0̂000, 1̂100, 0̂011, 1̂111}. By Corollary 3, |E(GEC)| = 16− 8− 2 = 6, that is, GEC is a complete graph. Theorem 4. Let GEC be the (k1, k2) E-torsion graph of a QSD code C = aB + cB⊥ where B is a binary code. Then B is self-dual if and only if GEC is a complete graph. Proof. Let B be self-dual. Then res(C) = tor(C). By Corollary 2, the degree of every vertex of GEC is 2k1+k2 − 1, J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1377 that is, GEC is a complete graph. Conversely, suppose that GEC is a complete graph. Let x ∈ tor(C). Then (x̂, ŷ) ∈ E(GEC) since GEC is complete. It follows that ax+ cy ∈ C for all y ∈ tor(C). Applying α, we have x ∈ res(C), that is, tor(C) ⊆ res(C). ■ Corollary 4. If C is a QSD code of type-(k1, 0), then GEC is a complete graph. Theorem 5. If C is a QSD code of type-(0, k2), then GEC is a star graph. Proof. If k1 = 0, then res(C) is the trivial code which contains only the zero vector. It follows that tor(C) = Fn 2 . Hence, E(GEC) = {(0̂v, x̂) : x ∈ Fn 2}. ■ Remark 1. Let k1, k2 ∈ Z+ and C1, C2 be type-(k1, k2) linear E-codes. Then GEC1 ∼= GEC2 . Looking at Remark 1, (k1, k2) E-torsion graph alone cannot be used to classify QSD codes since two inequivalent codes under the same type-(k1, k2) code have the same (k1, k2) E-torsion graph. So to separate these two inequivalent QSD codes, we use the concept of vertex-weighted graph which is defined in the following. Definition 3. The vertex-weighted (k1, k2) E-torsion graph of a QSD code is the vertex-weighted graph where the weight of a vertex x ∈ GEC is the weight of the codeword wt(x) of x ∈ tor(C). Example 3. Let C1 = aB1 + cB⊥ 1 and C2 = aB2 + cB⊥ 2 J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1378 where B1 = ⟨1100⟩ and B2 = ⟨1111⟩ . Note that C1 and C2 are two nonequivalents E-codes. Now, V (GEC1) = {0̂000, 1̂100, 0̂010, 1̂110, 0̂001, 1̂101, 0̂011, 1̂111} and V (GEC2) = {0̂000, 1̂111, 1̂100, 0̂011, 0̂110, 1̂001, 1̂010, 0̂101}. Figure 2 shows the graph representation of GEC1: Figure 2: (k1, k2) E-torsion graph of GEC1 Furthermore, Figure 3 is the graph representation of graph GEC2. Figure 3: (k1, k2) E-torsion graph of GEC2 Note that the two graphs are isomorphic. However, if we look at the vertex-weighted graph of GEC1 and GEC2 , respectively, (see Figure 4 and 5) using the weights of every codeword, we see the difference between these two vertex-weighted (1, 2) E-torsion graphs. Hence, two codes can have isomorphic graphs but different vertex-weighted (k1, k2) E- torsion graphs. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1379 Figure 4: (k1, k2) E-torsion graph of GEC1 Figure 5: (k1, k2) E-torsion graph of GEC2 5. Vertex-weighted (k1, k2) E-torsion graph of QSD codes with n ≤ 4 Quasi self-dual E-codes of short length were classified in [3]. In this section, we will illustrate those QSD codes using their vertex-weighted (k1, k2) E-torsion graphs up to n = 4. 5.1. (k1, k2) E-torsion graph of QSD codes for n=2. For C1 = a ⟨00⟩+ c ⟨10, 01⟩ , we have a (0, 2) E-torsion graph which is illustrated in Figure 6. Figure 6: Vertex-weighted (k1, k2) E-torsion graph of C1 J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1380 For C2 = a ⟨11⟩+ c ⟨11⟩ , we have a (1, 0) E-torsion graph which is illustrated in Figure 7. Figure 7: Vertex-weighted (k1, k2) E-torsion graph of C2 5.2. (k1, k2) E-torsion graph of QSD codes for n=3. For C3 = a ⟨000⟩+ c ⟨100, 010, 001⟩ , we have a (0, 3) E-torsion graph which is illustrated in Figure 8. Figure 8: Vertex-weighted (k1, k2) E-torsion graph of C3 5.3. (k1, k2) E-torsion graph of QSD codes for n=4. For C5 = a ⟨0000⟩+ c ⟨1000, 0100, 0010, 0001⟩ , we have a (0, 4) E-torsion graph which is illustrated in Figure 10. J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1381 For C4 = a ⟨101⟩+ c ⟨101, 010⟩ , we have a (1, 1) E-torsion graph which is illustrated in Figure 9. Figure 9: Vertex-weighted (k1, k2) E-torsion graph of C4 Figure 10: Vertex-weighted (k1, k2) E-torsion graph of C5 For C6 = a ⟨1100⟩+ c ⟨1100, 0010, 0001⟩ , we have a (1, 2) E-torsion graph which is illustrated in Figure 11. Figure 11: Vertex-weighted (k1, k2) E-torsion graph of C6 J. Pilongo, L. Paleta, P.L.Benjamin / Eur. J. Pure Appl. Math, 17 (2) (2024), 1369-1384 1382 For C7 = a ⟨1111⟩+ c ⟨1111, 1100, 0110⟩ , we have a (1, 2) E-torsion graph which is illustrated in Figure 12. Figure 12: Vertex-weighted (k1, k2) E-torsion graph of C7 For C8 = a ⟨1100, 0011⟩+ c ⟨1100, 0011⟩ , we have a (2, 0) E-torsion graph which is illustrated in Figure 13. Figure 13: Vertex-weighted (k1, k2) E-torsion graph of C8 REFERENCES 1383 6. Conclusion In this paper, we studied the (k1, k2) E-torsion graph of a type-(k1, k2) E-codes. In particular, the size of the set of vertices and set of edges. We also characterized (k1, k2) E-torsion graph when k1 = 0 and k2 = 0 and introduced the notion of vertex-weighted (k1, k2) E-torsion graph to differentiate inequivalent QSD codes of the same type. Finally, we were able to represent QSD codes which were classified in [3] up to n = 4 using the vertex-weighted (k1, k2) E-torsion graph. By defining a (k1, k2) E-torsion graph G such that the V (G) = 2k1+k2 , there are 2k1 vertices that have degree 2k1+k2 − 1 with the rest vertices, if there exist, have degree 2k1 . For future study, after graph operations of two (k1, k2) E-torsion graphs is a (k1, k2) E-torsion graph? Also, one can explore center of (k1, k2) E-torsion graphs and the dominating sets of (k1, k2) E-torsion graphs. References [1] A. Alahmadi, A. Alkathiry, A. Altassan, W. Basaffar, A. Bonnecaze, H. Shoaib, and P. Sole’. Quasi self-dual codes over non-unital rings of order six. Proyecciones (Antofagasta), 39(4):1083–1095, 2020. [2] A. Alahmadi, A. Alkathiry, A. Altassan, W. Basaffar, A. Bonnecaze, H. Shoaib, and P. Sole’. Type iv codes over a non-local non-unital ring. Proyecciones (Antofagasta, Online), 39(4):963–978, 2022. [3] A. Alahmadi, A. Altassan, W. Basaffar, A. Bonnecaze, and P. Sole’. Type iv codes over a non-unital ring. Journal of Algebra and Its Applications, 2(7), 2021. [4] A. Alahmadi, A. Melaibari, and P. Sole’. Duality of codes over non-unital rings of order four. IEEE Access, 2023. [5] S. T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Sole’. Type iv self-dual codes over rings. IEEE Trans. Information Theory, 45:2345–2360, 1999. [6] S. T. Dougherty, B. Yildiz, and S. Karadeniz. Self-dual codes over rk and binary self-dual codes. European Journal of Pure and Applied Mathematics, 6(1):89–106, 2013. [7] B. Fine. Classification of finite rings of order p2. Mathematics Magazine, 66(4):248– 252, 1993. [8] G. D. Forney. Codes on graphs: Fundamentals. IEEE Transactions on Information Theory, 60(10):5809–5826, 2014. [9] F. Harrary. Graph Theory. Addison-Wesley, 1994. [10] T. W. Hungerford. Algebra. Springer, 1974. REFERENCES 1384 [11] N. Nopendri, I. Muchtadi-Alamsyah, D. Suprijanto, and A. Barra. Cyclic codes from a sequence over finite fields. European Journal of Pure and Applied Mathematics, 14(3):685–694, 2021. [12] R. Raghavendran. Finite associative rings. Compositio Mathematica, 21(2):195–229, 1969. [13] S. E. Rouayheb and C. Georghiades. Graph theoretic methods in coding theory. In Springer eBooks, pages 53–62. 2011. [14] M. Shi, S. Wang, J. L. Kim, and P. Solé. Self-orthogonal codes over a non-unital ring and combinatorial matrices. Designs, Codes and Cryptography, pages 1–13, 2021. [15] B. Shinivasulu and M. Bhaintwal. Z2-triple cyclic codes and their duals. European Journal of Pure and Applied Mathematics, 10(2):392–409, 2016.