BINARY LINEAR CODES FROM SIMPLE GRAPHS

• Main Author: Dennis, Brandon
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/72980
• Institution: Institut Teknologi Bandung

Binary linear code C generated by a simple graph ? = (V,E) on n vertices is the linear code generated by [In|A] where In is the identity matrix of size n and A is the adjacency matrix of ?. The minimum distance of C can be found using the function von which maps set of vertices S of ? to another set of vertices von(S) containing vertices having odd number of neighbors in S. We extend upon the results of Mallik and Yildiz [Algebra and Discrete Matematics 32, 49–64 (2021)] by looking at the minimum distance and self-duality of codes generated by graphs and providing answers to the three open problems in Mallik and Yildiz’s article. In the first section of Chapter IV, we show some properties of the von function. In second section of Chapter IV, we give conditions for self-duality and an upper bound on the minimum distance of codes generated by graphs obtained from the graph operations of disjoint union, cartesian product, weak product, and strong product. In the first section of Chapter V, we define an optimal distance graph as the graph which generates code with minimum distance equals to rk2(A) + 1, with rk2(A) being the 2-rank of the adjacency matrix A of the graph. We show that only the complete graph on 3 vertices is an optimal distance graph. In the second section of Chapter V, we show conterexamples for the conjecture in the article of Mallik and Yildiz. In the third section of Chapter V, we discuss the minimum distance of codes generated by strongly regular graphs by enumerating the values for number of vertices not greater than 35.