Isodual and self-dual codes from graphs
Binary linear codes are constructed from graphs, in particular, by the generator matrix [In|A] where A is the adjacency matrix of a graph on n vertices. A combinatorial interpretation of the minimum distance of such codes is given. We also present graph theoretic conditions for such linear codes to...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2021
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188717 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Isodual and self-dual codes from graphs / S. Mallik, B. Yildiz // Algebra and Discrete Mathematics. — 2021. — Vol. 32, № 1. — С. 49–64. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188717 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1887172023-03-13T19:11:46Z Isodual and self-dual codes from graphs Mallik, S. Yildiz, B. Binary linear codes are constructed from graphs, in particular, by the generator matrix [In|A] where A is the adjacency matrix of a graph on n vertices. A combinatorial interpretation of the minimum distance of such codes is given. We also present graph theoretic conditions for such linear codes to be Type I and Type II self-dual. Several examples of binary linear codes produced by well-known graph classes are given. 2021 Article Isodual and self-dual codes from graphs / S. Mallik, B. Yildiz // Algebra and Discrete Mathematics. — 2021. — Vol. 32, № 1. — С. 49–64. — Бібліогр.: 15 назв. — англ. 1726-3255 DOI:10.12958/adm1645 2020 MSC: 94B05, 94B25. http://dspace.nbuv.gov.ua/handle/123456789/188717 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Binary linear codes are constructed from graphs, in particular, by the generator matrix [In|A] where A is the adjacency matrix of a graph on n vertices. A combinatorial interpretation of the minimum distance of such codes is given. We also present graph theoretic conditions for such linear codes to be Type I and Type II self-dual. Several examples of binary linear codes produced by well-known graph classes are given. |
| format |
Article |
| author |
Mallik, S. Yildiz, B. |
| spellingShingle |
Mallik, S. Yildiz, B. Isodual and self-dual codes from graphs Algebra and Discrete Mathematics |
| author_facet |
Mallik, S. Yildiz, B. |
| author_sort |
Mallik, S. |
| title |
Isodual and self-dual codes from graphs |
| title_short |
Isodual and self-dual codes from graphs |
| title_full |
Isodual and self-dual codes from graphs |
| title_fullStr |
Isodual and self-dual codes from graphs |
| title_full_unstemmed |
Isodual and self-dual codes from graphs |
| title_sort |
isodual and self-dual codes from graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2021 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188717 |
| citation_txt |
Isodual and self-dual codes from graphs / S. Mallik, B. Yildiz // Algebra and Discrete Mathematics. — 2021. — Vol. 32, № 1. — С. 49–64. — Бібліогр.: 15 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT malliks isodualandselfdualcodesfromgraphs AT yildizb isodualandselfdualcodesfromgraphs |
| first_indexed |
2025-07-16T10:54:21Z |
| last_indexed |
2025-07-16T10:54:21Z |
| _version_ |
1837800633346818048 |
| fulltext |
“adm-n3” — 2021/11/8 — 20:27 — page 49 — #51
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 32 (2021). Number 1, pp. 49–64
DOI:10.12958/adm1645
Isodual and self-dual codes from graphs
S. Mallik and B. Yildiz
Communicated by V. A. Artamonov
Abstract. Binary linear codes are constructed from graphs,
in particular, by the generator matrix [In|A] where A is the adjacency
matrix of a graph on n vertices. A combinatorial interpretation of
the minimum distance of such codes is given. We also present graph
theoretic conditions for such linear codes to be Type I and Type
II self-dual. Several examples of binary linear codes produced by
well-known graph classes are given.
1. Introduction
There is a strong connection between graphs and codes. The adjacency
matrix of a simple graph is a symmetric binary matrix which has made it
suitable for constructing binary codes. Depending on the structure of the
graphs, special types of codes can be obtained.
We start with some basic definitions about codes that will be used
throughout the paper. Let F2 be the binary field. A binary linear code
C of length n is defined as a subspace of Fn
2 . If the dimension of C is k,
we say C is an [n, k]-code. A matrix whose rows form a basis for C is
called a generator matrix for C and is denoted by G. We also denote C by
C(G). By using elementary row and column operations, we can bring the
generator matrix G into a standard form [Ik|A] where A is a k × (n− k)
matrix. Two binary codes are said to be equivalent if one can be obtained
from the other by a permutation of coordinates.
2020 MSC: 94B05, 94B25.
Key words and phrases: self-dual codes, isodual codes, graphs, adjacency matrix,
strongly regular graphs.
https://doi.org/10.12958/adm1645
“adm-n3” — 2021/11/8 — 20:27 — page 50 — #52
50 Isodual and self-dual codes from graphs
The Hamming weight wH(x) of a vector x ∈ F
n
2 is defined as the
number of non-zero coordinates in x. The Hamming distance between two
vectors x and y in F
n
2 , denoted by dH(x,y), is defined as
dH(x,y) = wH(x− y).
The minimum distance of a code C, denoted by d(C), is defined to be
the minimum distance between distinct codewords in C. We write the
standard parameters [n, k, d] to describe a code C where n denotes the
length of C, k its dimension, and d its minimum distance.
Definition 1. Let C be a binary linear code of length n. The dual of C,
denoted by C⊥, is given by
C⊥ := {y ∈ F
n
2 | 〈y,x〉 = 0 ∀ x ∈ C}.
Note that, if C is a linear [n, k]-code, then C⊥ is a linear [n, n−k]-code.
Definition 2. A binary linear code C is self-orthogonal if C ⊆ C⊥ and
self-dual if C = C⊥.
Definition 3. Let C be a self-dual binary code. If the Hamming weights
of all the codewords in C are divisible by 4, then C is called Type II (or
doubly-even), otherwise it is called Type I (or singly even).
The following theorem gives an upper bound for the minimum distance
of self-dual codes:
Theorem 1 ([13]). Let dI(n) and dII(n) be the minimum distances of a
Type I and Type II binary code of length n respectively. Then
dII(n) 6 4⌊
n
24
⌋+ 4
and
dI(n) 6
{
4⌊ n
24
⌋+ 4 if n 6≡ 22 (mod 24)
4⌊ n
24
⌋+ 6 if n ≡ 22 (mod 24).
Self-dual codes that attain the bounds given in the previous theorem
are called extremal.
Definition 4. A binary code C is said to be isodual if it is permutation
equivalent to its dual.
Theorem 2. If C is generated by G = [Ik|A], then the generator matrix
of C⊥ is given by H = [−AT |Ik].
“adm-n3” — 2021/11/8 — 20:27 — page 51 — #53
S. Mallik, B. Yildiz 51
H is also called the parity-check matrix of C, namely C is given by
C = {c ∈ F
n
2 |HcT = 0}.
There is a natural connection between the parity-check matrix of a
linear code and the minimum distance which is given by the following
theorem:
Theorem 3. Let C be a linear code and H a parity check matrix for C.
Then
(i) d(C) > d if and only if any d − 1 columns of H are linearly
independent.
(ii) d(C) 6 d if and only if H has d columns that are linearly depen-
dent.
Corollary 1. If C is a linear code and H is a parity check matrix for C,
then C has minimum distance d if and only if any d − 1 columns of H
are linearly independent and some d columns of H are linearly dependent.
The connection of codes and graphs has been explored from different
aspects in the literature. The main theme in these works is to take a
special class of graphs and construct codes from the adjacency matrix of
the graph. The structure of the graph may lead to different types of codes
as a result, such as self-dual codes, self-orthogonal codes, etc. We refer
the reader to [2]–[12], [14] and [15] for some of these works.
In this work we focus on the following type of construction which was
discussed in [15]. Let A be the adjacency matrix of a simple graph on
n vertices. We construct the binary code C from the generator matrix
[In|A]. Such a construction has several advantages which we can describe
as follows:
1) The dimension of the codes is automatically determined as n. So
we are looking at [2n, n]-codes.
2) A parity-check matrix of such a code is given by [AT |In] = [A|In]
since A is symmetric
3) Note that a permutation of columns of [A|In] will bring the matrix
into [In|A], which means any such code C is isodual.
4) Since the codes are isodual, to determine the conditions for self-
duality, we just need to factor in the orthogonality conditions.
In addition to the conditions on the graph that would ensure self-
duality of the constructed code, we also find upper bounds on the minimum
distances of codes obtained via this construction. We give a combinatorial
“adm-n3” — 2021/11/8 — 20:27 — page 52 — #54
52 Isodual and self-dual codes from graphs
description to the exact minimum distances of such codes as well as
codes obtained from just the adjacency matrix A as the generator matrix.
We give examples of isodual and self-dual codes obtained through this
construction.
The rest of the work is organized as follows. In section 2, we give the
upper bounds and combinatorial descriptions for the minimum distances of
codes obtained from graphs. In section 3, we give necessary and sufficient
conditions for the codes to be self-dual, Type I and Type II. In addition,
we describe how the join operation on graphs affects the self-duality
conditions. We give several examples of self-dual codes obtained through
the construction.
2. The [In|A] construction for codes
As was mentioned in the Introduction, we focus mainly on the con-
struction of binary codes generated by [In|A] where A is the adjacency
matrix of a simple graph. We start with the following observation:
Observation 4. Linear codes generated by [In|A] and [In|PAP T ], where
P is a permutation matrix, are not necessarily the same. For example,
consider the graph P3 with adjacency matrix A and permutation matrix
P generated by (1, 2):
[I3|A] =
1 0 0 0 1 0
0 1 0 1 0 1
0 0 1 0 1 0
[I3|PAP T ] =
1 0 0 0 1 1
0 1 0 1 0 0
0 0 1 1 0 0
(1, 0, 0, 0, 1, 0) ∈ C([I3|A]) = {(a, b, c, b, a+ c, b) | a, b, c ∈ F2}
(1, 0, 0, 0, 1, 0) /∈ C([I3|PAP T ]) = {(a, b, c, b+ c, a, a) | a, b, c ∈ F2}.
It is not obvious that C([I3|A]) and C([I3|PAP T ]) have the same
minimum distance.
The following result gives an upper bound of the minimum distance of
a binary code in terms of the 2-rank (see [1]) of the corresponding graph.
Theorem 5. Let A be the adjacency matrix of a graph on n vertices and
let C be the binary linear code generated by [In|A]. Then we have
d(C) 6 rk2(A) + 1,
“adm-n3” — 2021/11/8 — 20:27 — page 53 — #55
S. Mallik, B. Yildiz 53
where rk2(A) denotes the rank of A as a matrix over F2.
Proof. Let G = [In|A] be the generator matrix of C. Then H = [−AT |In]
= [A|In] is the parity-check matrix of C. By the definition of the rank,
any set of rk2(A) + 1 columns of A are linearly dependent. By Theorem 2,
d(C) 6 rk2(A) + 1.
To get a combinatorial interpretation of the minimum distance of
C([In|A]), we study the following set of vertices of a graph Γ with adjacency
matrix A and vertex set V : for a nonempty subset S of V , the set of vertices
of Γ with odd number of neighbors in S is denoted by von(S), i.e.,
von(S) = {v ∈ V : |N(v) ∩ S| is odd},
where N(v) denotes the set of neighbors of the vertex v in Γ. Note that
S and von(S) have no inclusion-exclusion relationship that holds for all
graphs as evident in the following examples.
Example 1.
1) Consider Γ = C4 with vertices 1, 2, 3, 4 consecutively adjacent. For
S = {1}, von(S) = {2, 4} = N(1). For S = {1, 2}, von(S) =
{1, 2, 3, 4}. For S = {1, 3}, von(S) = ∅.
2) Consider Γ = Kn, n > 4 with vertex set {1, 2, . . . , n}. For S = {1},
von(S) = {2, 3, . . . , n} = N(1). For S = {1, 2}, von(S) = {1, 2}.
For S = {1, 2, . . . , n − 1} with even n, von(S) = {n}. For S =
{1, 2, . . . , n− 1} with odd n, von(S) = {1, 2, . . . , n− 1}.
Definition 5. Two vertices u and v of a graph are called duplicate ver-
tices if they are not adjacent and N(u) = N(v), i.e., they have the same
neighbors.
Observation 6. Let Γ be a graph. If S is a set of two duplicate vertices
of Γ, then von(S) = ∅.
Proof. Let A be the adjacency matrix of Γ and Ai denote the column i
of A. Without loss of generality, let S = {1, 2}. If 1 and 2 are duplicate
vertices, then A1 +A2 ≡ 0 (mod 2) which implies von(S) = ∅.
Linear dependency relations among columns of a matrix associated
with graphs have been studied in [11]. We study the same in connection
with von.
“adm-n3” — 2021/11/8 — 20:27 — page 54 — #56
54 Isodual and self-dual codes from graphs
Theorem 7. Let G be a graph with vertex set V and adjacency matrix A.
Let S be a nonempty subset of V . If von(S) = ∅, then the columns of A
corresponding to S are linearly dependent. Conversely, if the columns of
A corresponding to S are minimally linearly dependent, then von(S) = ∅.
Proof. Suppose S = {i1, i2, . . . , ik} and von(S) = ∅. Then
Ai1 +Ai2 + · · ·+Aik ≡ 0 (mod 2)
which implies columns Ai1 , Ai2 , . . . , Aik of A are linearly dependent.
Conversely, suppose S = {1, 2, . . . , k} and A1, A2, . . . , Ak are min-
imally linearly dependent. Then A1 + A2 + · · · + Ak ≡ 0 (mod 2). If
i ∈ von(S), then
(A1 +A2 + · · ·+Ak)i ≡ 1 (mod 2) ,
a contradiction. Thus von(S) = ∅.
Corollary 2. Let Γ be a graph with vertex set V and adjacency matrix
A. Let S be a nonempty subset of V . The columns of A corresponding to
S are minimally linearly dependent if and only if one of the following is
true:
(a) S consists of a single isolated vertex of Γ.
(b) von(S \ {i}) = N(i) for each i ∈ S and there is no proper subset S′
of S for which von(S′ \ {i}) = N(i) for each i ∈ S′.
Now we discuss linear dependence among columns of [A|In] where A
is the adjacency matrix of a graph Γ on n vertices.
Theorem 8. Let Γ be a graph on n vertices with vertex set V and adjacency
matrix A. If S is a nonempty subset of V , then the columns of A indexed
by S and the columns of In indexed by von(S) are (|S|+ | von(S)|) linearly
dependent columns of [A|In]. Conversely, if the set of columns of [A|In]
indexed by the set S′ ⊆ {1, 2, . . . , 2n} is minimally linearly dependent,
then it is the union of the columns of A indexed by S and the columns of
In indexed by von(S) for some nonempty subset S of V , in other words
S′ = S ∪ {n+ i | i ∈ von(S)}.
Proof. Let ∅ 6= S ⊆ V . Let c be the sum of columns of A indexed by
S. Then ci, the ith entry of c, is the number of vertices of S adjacent to
vertex i. Therefore if vertex i is adjacent to an even number of vertices in
S, then ci ≡ 0 (mod 2). Similarly if vertex i is adjacent to an odd number
of vertices in S, then ci ≡ 1 (mod 2). Thus the only entries of c that are
“adm-n3” — 2021/11/8 — 20:27 — page 55 — #57
S. Mallik, B. Yildiz 55
1 (mod 2) correspond to von(S). So if we add c with the columns of In
with indices corresponding to von(S), the sum would be a zero vector.
Conversely, suppose the set of d columns of [A|In] indexed by the
set S′ ⊆ {1, 2, . . . , 2n} is minimally linearly dependent. Without loss
of generality suppose S′ is the union of S = {1, 2, . . . , k}, k 6 n and
T ⊆ {n+ 1, n+ 2, . . . , 2n}.
Case 1. T = ∅ (i.e., S′ = S)
Since A1, A2, . . . , Ak are minimally linearly dependent,A1+A2+· · ·+Ak ≡
0 (mod 2). It suffices to show that von(S) = ∅. If not, let i ∈ von(S).
Then
(A1 +A2 + · · ·+Ak)i ≡ 1 (mod 2) ,
a contradiction.
Case 2. T 6= ∅
Let T = {n + i1, n + i2, . . . , n + id−k} and ej be column j of In for
j = i1, i2, . . . , id−k. Since A1, A2, . . . , Ak, ei1 , ei2 , . . . , eid−k
are minimally
linearly dependent,
A1 +A2 + · · ·+Ak + ei2 + · · ·+ eid−k
≡ 0 (mod 2) .
Then
A1 +A2 + · · ·+Ak ≡ ei1 + ei2 + · · ·+ eid−k
(mod 2)
which implies von(S) = {i1, i2, . . . , id−k} because ei1 , ei2 , . . . , eid−k
are
columns of In. Thus S′ = S ∪ {n+ i | i ∈ von(S)}.
As a consequence of the preceding theorem, we have the following
result.
Theorem 9. Let A be the adjacency matrix of a graph Γ on n vertices
with vertex set V . Let C be the binary linear code generated by [In|A].
Then the minimum distance d(C) of C is given by
d(C) = min
∅ 6=S⊆V
(|S|+ | von(S)|).
Proof. First note that H = [A|In] is the parity-check matrix of C. By
Theorem 8, a codeword in C with weight d(C) corresponds to minimally
dependent columns of H = [A|In] indexed by S ∪ {n+ i | i ∈ von(S)} for
some nonempty subset S of V . Then
d(C) > min
∅ 6=S⊆V
(|S|+ | von(S)|).
“adm-n3” — 2021/11/8 — 20:27 — page 56 — #58
56 Isodual and self-dual codes from graphs
If there is a nonempty subset S of V for which d(C) > |S| + | von(S)|,
then by Theorem 8 we find (|S|+ | von(S)|) linearly dependent columns
of H = [A|In] giving a codeword of C with weight less than d(C), a
contradiction. Thus the equality holds.
Corollary 3. Let A be the adjacency matrix of a graph Γ on n vertices.
Let P be an n × n permutation matrix. Then the binary linear codes
generated by [In|A] and [In|PAP T ] are not necessarily the same but they
have the same minimum distance.
Proof. The graph with adjacency matrix PAP T is isomorphic to Γ. Then
the binary linear codes generated by [In|A] and [In|PAP T ] have the same
minimum distance by Theorem 9.
By Theorem 5 and Theorem 9, we have the following lower bound of
the 2-rank of a graph:
Corollary 4. Let A be the adjacency matrix of a graph Γ with vertex
set V . Then
−1 + min
∅ 6=S⊆V
(|S|+ | von(S)|) 6 rk2(A).
Question 10. Characterize the graphs Γ with the adjacency matrix A
and the vertex set V for which
rk2(A) = −1 + min
∅ 6=S⊆V
(|S|+ | von(S)|).
Example 2. The following are examples of binary linear code C generated
by [In|A] where A is the adjacency matrix of a graph Γ on n vertices.
1) For Γ = Pn, n > 2, d(C) = 2 = |S|+ | von(S)| where S = {1} and
von(S) = {2}.
For Γ = P1, d(C) = 1 = |S|+ | von(S)| where S = {1} and von(S) =
∅.
2) When Γ is a tree on n > 2 vertices, d(C) = 2 = |S|+ | von(S)| where
S = {v} consisting of a pendant vertex v and von(S) = {w} where
w is adjacent to v.
3) For Γ = Cn, n > 5, d(C) = 3 = |S|+ | von(S)| where S = {1} and
von(S) = {2, n}.
For Γ = C4, d(C) = 2 = |S| + | von(S)| where S = {1, 3} and
von(S) = ∅.
For Γ = C3, d(C) = 3 = |S| + | von(S)| where S = {1} and
von(S) = {2, 3}.
“adm-n3” — 2021/11/8 — 20:27 — page 57 — #59
S. Mallik, B. Yildiz 57
4) For Γ = Kn, n > 4, d(C) = 4 = |S| + | von(S)| where S = {1, 2}
and von(S) = {1, 2}.
5) For star Γ = K1,n, n > 1 centered at 1, d(C) = 2 = |S|+ | von(S)|
where S = {2} and von(S) = {1}.
6) For Γ = Km,n, m or n > 2, d(C) = 2 = |S| + | von(S)| where
S = {1, 2} and von(S) = ∅ because of duplicate vertices 1 and 2.
Recall C4 = K2,2.
7) For G = Wn = K1 ∨ Cn−1, n > 6 centered at 1, d(C) = 4 =
|S|+ | von(S)| where S = {2} and von(S) = {1, 3, n}.
For Γ = W5, d(C) = 2 = |S| + | von(S)| where S = {2, 4} and
von(S) = ∅.
For Γ = W4, d(C) = 4 = |S| + | von(S)| where S = {1} and
von(S) = {2, 3, 4}.
8) When Γ is the Petersen graph which is the srg(10, 3, 0, 1), d(C) =
4 = |S| + | von(S)| where S = {1} and von(S) = N(1) = {2, 5, 6}
where the outer vertices are 1,2,3,4 in the standard drawing.
Remark 1. Suppose V is the vertex set of Kn and let S ⊆ V . It is easy
to observe that
von(S) =
{
S if |S| is even
V \ S if |S| is odd.
Observation 11. Let A be the adjacency matrix of a graph Γ on n vertices
with vertex set V . Let C be the binary linear code generated by [In|A] and
S be a nonempty subset of V for which d(C) = |S|+ | von(S)|. From the
preceding remark for Kn, we have either S = von(S) or S ∩ von(S) = ∅.
At least one of these two properties seems to hold for other graphs also.
Conjecture 12. Let A be the adjacency matrix of a graph Γ on n vertices
with vertex set V . Let C be the binary linear code generated by [In|A].
Suppose S is a nonempty subset of V for which d(C) = |S| + | von(S)|.
Then either S = von(S) or S ∩ von(S) = ∅.
The following observation may be helpful for the future work on the
preceding conjecture.
Observation 13. If v ∈ S ∩ von(S) and |S| > 2, then
von(S\{v})\N(v) = von(S)\N(v) and von(S\{v})∩von(S)∩N(v) = ∅.
“adm-n3” — 2021/11/8 — 20:27 — page 58 — #60
58 Isodual and self-dual codes from graphs
3. Self-dual codes from graphs
We start by observing that if A is an n× n matrix, then the binary
code generated by [In|A] is a self-dual code if and only if AAT = In, where
the matrix multiplication is done in F2. If A is the adjacency matrix of
a simple graph, then this condition is reduced to A2 ≡ In (mod 2). We
first give some results on the graphs for which this condition is satisfied.
Theorem 14. Let Γ be a graph on n vertices 1, 2, . . . , n with adjacency
matrix A. Then A2 ≡ In (mod 2) if and only if the following are true:
(a) deg(i) is odd for all vertices i = 1, 2, . . . , n (This implies n is even).
(b) |N(i) ∩N(j)| is even for all vertices i 6= j.
Proof. Suppose A2 ≡ In (mod 2). Then for all i = 1, 2, . . . , n,
∑n
k=1
a2ik
≡ 1 (mod 2), i.e.,
∑n
k=1
a2ik is odd and consequently deg(i) is odd. Since
every graph has an even number of odd-degree vertices, n is even by
(a). Since A2 ≡ In (mod 2), for all vertices i 6= j,
∑n
k=1
aikajk is even
and consequently |N(i) ∩N(j)| is even. The converse follows by similar
arguments.
We prove the following lemma which will be used in the proof of the
subsequent theorem:
Lemma 1. Let C be a self-orthogonal code and assume c1, c2 are two
codewords with
w(c1) ≡ w(c2) ≡ 0 (mod 4).
Then w(c1 + c2) ≡ 0 (mod 4).
Proof. Since C is self-orthogonal, we have 〈c1, c2〉 = 0, which implies the
weight w(c1 ◦ c2) of the entry-wise product c1 ◦ c2 of c1 and c2 is even.
Thus we have
w(c1 + c2) = w(c1) + w(c2)− 2w(c1 ◦ c2) ≡ 0 (mod 4).
We are now ready to prove the following theorem which gives a neces-
sary and sufficient condition for a graph to generate a Type II code:
Theorem 15. Let A be the adjacency matrix of a simple graph on n ver-
tices, which satisfies the hypothesis of Theorem 14. Then [In|A] generates
a Type II code if and only if deg(v) ≡ 3 (mod 4) for all vertices v of the
graph.
“adm-n3” — 2021/11/8 — 20:27 — page 59 — #61
S. Mallik, B. Yildiz 59
Proof. The necessity being clear, we proceed to proving the sufficiency.
Suppose deg(v) ≡ 3 (mod 4) for all vertices v. Then each row of
G = [In|A] has weight divisible by 4. Suppose the rows of G are denoted
by r1, r2, . . . , rn. So we have w(ri) ≡ 0 (mod 4) for i = 1, 2, . . . , n. Then
we claim that all the codewords will have weight divisible by 4. Note
that every codeword of C([In|A]) is obtained from a sum of the form
ri1 + ri2 + · · · + rik , where 1 6 i1 < i2 < · · · < ik 6 n and k > 1. We
proceed by induction on k.
If k = 1, then we have just the rows ri, which all have weights divisible
by 4.
Assume the assertion to be true for all sums with k > 1 summands.
Let
c = ri1 + ri2 + · · ·+ rik + rik+1
= (ri1 + ri2 + · · ·+ rik) + rik+1
.
By induction hypothesis, (ri1 + ri2 + · · ·+ rik) has weight divisible by
4. Note that both (ri1 + ri2 + · · ·+ rik) and rik+1
are codewords in C,
which is self-dual and both codewords have weights divisible by 4. So by
Lemma 1, the weight of c is divisible by 4.
Since Type II binary self-dual codes only exist for lengths that are
multiple of 8, we have the following combinatorial result as a consequence
of the previous theorem:
Corollary 5. Let n ≡ 2 (mod 4). Then a simple graph on n vertices that
satisfies the hypotheses of Theorem 14 has at least one vertex whose degree
is 1 (mod 4).
In the following theorem, we explore the special case of complete
graphs.
Theorem 16. Let C be the code generated by [In|A], where A is the
adjacency matrix of Kn. C is a self-dual code if and only if n is even.
Moreover, if n > 4 we have
a) C is a Type II self-dual code of parameters [2n, n, 4] if n is divisible
by 4.
b) C is a Type I self-dual code of parameters [2n, n, 4] if n is not
divisible by 4.
Proof. By Theorem 14, C is self-dual if and only if n is even.
a) If n = 4k, then the degree of every vertex of Kn is 4k − 1, which,
by Theorem 15, implies that the code generated by [In|A] is Type II. This
“adm-n3” — 2021/11/8 — 20:27 — page 60 — #62
60 Isodual and self-dual codes from graphs
means d(C) > 4. But the sum of any two rows of [In|A] has weight 4,
which means d(C) = 4.
b) If n = 4k + 2 with k > 1, then every row of [In|A] has weight
4k + 2, which makes C Type I. To find the minimum distance, we use
Theorem 9. Let S be a nonempty subset of the vertices of Kn. If S = {x},
then | von(S)| = n− 1, which means |S|+ | von(S)| = n > 4.
If S = {x, y}, then von(S) = S, which means |S|+ | von(S)| = 4.
If S = {x, y, z}, then | von(S)| = n− 3, which means |S|+ | von(S)| =
n > 4.
If |S| > 4, then |S| + | von(S)| > 4. Thus the minimum distance is
4.
Corollary 6. The code generated by Kn is an extremal Type II self-dual
code for n = 4 and n = 8. The code generated by Kn is an extremal Type
I self-dual code for n = 6.
Example 3. Consider the regular graph Γ = 2K4 which is the strongly
regular graph srg(8, 3, 2, 0) with the following adjacency matrix A. Since
A2 ≡ I8 (mod 2) and each vertex of Γ has degree 3, the binary code C =
C([I8|A]) is an extremal Type II self-dual [16, 8, 4] code by Theorems 14, 15,
and 1.
A =
0 0 0 1 0 1 0 1
0 0 1 0 1 0 1 0
0 1 0 0 1 0 1 0
1 0 0 0 0 1 0 1
0 1 1 0 0 0 1 0
1 0 0 1 0 0 0 1
0 1 1 0 1 0 0 0
1 0 0 1 0 1 0 0
Theorem 17. Let Γ be a strongly regular graph with parameters (n, k, λ,
µ) and adjacency matrix A. Suppose C is a linear code generated by [In|A].
Then C is self-dual if and only if k is odd and n, λ, µ are even.
Proof. For a strongly regular graph with parameters (n, k, λ, µ), deg(i) = k
for all i = 1, 2, . . . , n and |N(i) ∩N(j)| is λ or µ for all i 6= j. Thus A2 ≡
In (mod 2) if and only if k is odd and λ, µ are even by Theorem 14.
Question 18. Let Γ be a strongly regular graph with parameters (n, k, λ,
µ) and adjacency matrix A. Find the minimum distance of the linear code
C([In|A]) in terms of n, k, λ, µ.
“adm-n3” — 2021/11/8 — 20:27 — page 61 — #63
S. Mallik, B. Yildiz 61
Now we explore effects of graph operations on corresponding linear
codes. In particular, we study the join Γ1 ∨ Γ2 of two graphs Γ1 and Γ2
with disjoint vertex sets V1 and V2 respectively. Note that Γ1 ∨ Γ2 has the
vertex set V1 ∪ V2 and the edge set consisting of all edges of Γ1 and Γ2
together with all edges between them. For example, Km,n is the join of
mK1 and nK1.
Theorem 19. Let Γ1 and Γ2 be two graphs on n1 and n2 vertices with
adjacency matrices A1 and A2 respectively. Suppose Γ1 ∨ Γ2 is the join of
Γ1 and Γ2 with adjacency matrix A. If C([In1
|A1]) and C([In2
|A2]) are
self-dual codes, then so is C([In1+n2
|A]).
Proof. First note that
A =
[
A1 Jn1,n2
Jn2,n1
A2
]
and
A2 =
[
n2Jn1,n1
+A2
1 A1Jn1,n2
+ Jn1,n2
A2
Jn2,n1
A1 +A2Jn2,n1
n1Jn2,n2
+A2
2
]
.
Suppose C([In1
|A1]) and C([In2
|A2]) are self-dual codes. By Theo-
rem 14, A2
1 ≡ In1
(mod 2) and A2
2 ≡ In2
(mod 2) which imply n1 ≡ n2 ≡ 0
(mod 2) and degree of each vertex in Γ1 and Γ2 is 1 (mod 2). Then
A1Jn1,n2
+ Jn1,n2
A2 ≡ Jn1,n2
+ Jn1,n2
≡ On1,n2
(mod 2),
Jn2,n1
A1 +A2Jn2,n1
≡ Jn2,n1
+ Jn2,n1
≡ On2,n1
(mod 2).
A2 =
[
n2Jn1,n1
+A2
1 A1Jn1,n2
+ Jn1,n2
A2
Jn2,n1
A1 +A2Jn2,n1
n1Jn2,n2
+A2
2
]
≡ In1+n2
(mod 2).
Thus C([In1+n2
|A]) is a self-dual code by Theorem 14.
The following theorem describes the type of the join of self-dual codes.
Theorem 20. Let Γ1 and Γ2 be two graphs on n1 and n2 vertices and
with generator matrices A1 and A2 respectively. Suppose that A is the
generator matrix of Γ1 ∨ Γ2.
(a) When n1 ≡ n2 ≡ 0 (mod 4), C([In1+n2
|A]) is Type II if and only if
both C([In1
|A1]) and C([In2
|A2]) are Type II.
“adm-n3” — 2021/11/8 — 20:27 — page 62 — #64
62 Isodual and self-dual codes from graphs
(b) When n1 ≡ n2 ≡ 2 (mod 4), if C([In1+n2
|A]) is Type II, then both
C([In1
|A1]) and C([In2
|A2]) are Type I and the converse is true if
each vertex of Γ1 and Γ2 has degree 1 (mod 4).
(c) If exactly one of n1 and n2 is divisible by 4, then C([In1+n2
|A]) is
Type I.
Proof. First we observe that for any vertex v in Γ1, the degree of v in
Γ1 ∨ Γ2 is n2 + deg(v). Similarly for any vertex w in Γ2, the degree of
w in Γ1 ∨ Γ2 is n1 + deg(w). Then the cases n1 ≡ n2 ≡ 0 (mod 4) and
n1 ≡ n2 ≡ 2 (mod 4) follow from Theorem 15.
Now consider the case when exactly one of n1 and n2 is divisible by
4. Then we have n1 + n2 ≡ 2 (mod 4), which implies 2(n1 + n2) ≡ 4
(mod 8). Since Type II codes only exist for lengths that are multiples of
8, C([In1+n2
|A]) is not Type II, hence Type I.
We end by the following results about the minimum distance of
C([In1+n2
|A]) and its connection to the minimum distances of C([In1
|A1])
and C([In2
|A2]).
Theorem 21. Let Γ1 and Γ2 be two graphs with disjoint vertex sets V1
and V2 of sizes n1 and n2 respectively. Let A1, A2, and A be the adjacency
matrices of Γ1, Γ2, and Γ1 ∨ Γ2 respectively. Suppose that d1, d2, and d
are the minimum distances of the codes generated by [In1
|A1], [In2
|A2],
and [In1+n2
|A] respectively.
(a) Suppose Si is a nonempty subset of Vi for which di = |Si|+ | von(Si)|
for i = 1, 2. If |Si| is even for some i = 1, 2, then
d 6 di.
If |S1| and |S2| are odd, then
d 6 min{n2 + d1, n1 + d2}.
(b) Suppose S = S1 ∪ S2 is a nonempty subset of V1 ∪ V2 for which
d = |S|+ | von(S)| where ∅ 6= S1 ⊆ V1 and ∅ 6= S2 ⊆ V2. If at least
one of |S1| and |S2| is even, then
d1 + d2 6 d.
Proof. (a) We prove this by the following cases:
Case 1. |S1| is even.
For S = S1 ⊆ V1 ∪ V2 in Γ1 ∨ Γ2, we have von(S) = von(S1) in Γ1. Then
by Theorem 9,
d 6 |S1|+ | von(S1)| = d1.
“adm-n3” — 2021/11/8 — 20:27 — page 63 — #65
S. Mallik, B. Yildiz 63
Case 2. |S2| is even.
For S = S2 ⊆ V1 ∪ V2 in Γ1 ∨ Γ2, we have von(S) = von(S2) in Γ2. Then
by Theorem 9,
d 6 |S2|+ | von(S2)| = d2.
Case 3. |S1| and |S2| are odd.
In Γ1 ∨ Γ2, let S = S1. Thus von(S) = von(S1) ∪ V2. Then by Theorem 9,
d 6 |S1|+ | von(S1)|+ |V2| = n2 + d1.
Similarly
d 6 |S2|+ | von(S2)|+ |V1| = n1 + d2.
(b) We prove this by the following cases:
Case 1. |S1| and |S2| are even.
von(S) is the union of von(S1) in Γ1 and von(S2) in Γ2. Then by Theo-
rem 9,
d1 + d2 6 |S1|+ |S2|+ | von(S1)|+ | von(S2)| = d.
Case 2. |S1| is odd and |S2| is even.
von(S) is the union of V2 and von(S1) in Γ1. Then by Theorem 9,
d1 + d2 6 |S1|+ |S2|+ | von(S1)|+ |V2| = d.
Case 3. |S1| is even and |S2| is odd.
Similar to Case 2, we have
d1 + d2 6 d.
References
[1] A. Abiad, W. H. Haemers, “Switched symplectic graphs and their 2-ranks", Des.
Codes Crypt., vol. 81, no. 1, pp. 35–41, 2016.
[2] D. Crnković, B.G. Rodrigues, S. Rukavina and L. Simčić, “Ternary codes from the
strongly regular (45, 12, 3, 3) graphs and orbit matrices of 2-(45, 12, 3) designs",
Discrete Math., vol. 312, no. 20, pp. 3000–3010, 2012.
[3] D. Crnković, M. Maximović, B. Rodrigues and S. Rukavina, “Self-orthogonal codes
from the strongly regular graphs on up to 40 vertices", Adv. Math. Communications,
vol. 10, no. 3, pp. 555–582, 2016.
[4] P. Dankelmann, J.D. Key and B. G. Rodrigues, “A Characterization of Graphs by
Codes from their Incidence Matrices", Elect. J. Combinatorics, vol. 20, no. 3, P18,
2013.
[5] W. Fish, R. Fray and E. Mwambene, “Binary codes from the complements of the
triangular graphs", Quaestiones Mathematicae, vol. 33, no. 4, pp. 399–408, 2010.
“adm-n3” — 2021/11/8 — 20:27 — page 64 — #66
64 Isodual and self-dual codes from graphs
[6] G. D. Forney, “Codes on Graphs: Fundamentals", arXiv:1306.6264
[7] C. D. Godsil and G. F. Royle, “Chromatic Number and the 2-Rank of a Graph ",
J. Comb. Series B, vol. 81, pp. 142–149, 2001.
[8] M. Grassl and M. Harada, “New self-dual additive F4-codes constructed from
circulant graphs", Discrete Math., vol. 340, no. 3, pp.399–403, 2017.
[9] J.D. Key and B.G. Rodrigues, “LCD codes from adjacency matrices of graphs",
Appl. Alg. Eng. Comm. Comp., vol. 29, no. 3, pp.227–244, 2018.
[10] K. Kumwenda and E. Mwambene, “Codes from graphs related to the categorical
product of triangular graphs and Kn", IEEE Trans. Inform. Theory Workshop,
ITW 2010 Dublin.
[11] S. Mallik and B. L. Shader, “Classes of graphs with minimum skew rank 4", Linear
Algebra Appl. 439 (2013) 3643–3657.
[12] H. Oral, “Self-dual Codes and Graphs", Thesis, Simon Frasier University, 1989.
[13] E.M. Rains, “Shadow Bounds for Self Dual Codes", IEEE Trans. Inf. Theory,
vol.44, pp.134–139, 1998.
[14] V. Tonchev, “Error-correcting codes from graphs", Discrete Math., vol. 257, no.
2-3, pp.549–557, 2002.
[15] V. Tonchev, “Rank-3 Graphs, Block Designs, and Codes with Unequal Symbol
Protection", Problemy Peredaci Informatsii, vol. 17, no. 2, pp.89–93, 1981.
Contact information
Sudipta Mallik Department of Mathematics and Statistics,
Northern Arizona University,
801 S. Osborne Dr. PO Box: 5717, Flagstaff,
AZ 86011, USA
E-Mail(s): sudipta.mallik@nau.edu
Web-page(s): http:
//oak.ucc.nau.edu/sm2825/
Bahattin Yildiz Department of Mathematics and Statistics,
Northern Arizona University,
801 S. Osborne Dr. PO Box: 5717, Flagstaff,
AZ 86011, USA
E-Mail(s): bahattin.yildiz@nau.edu
Web-page(s): profile.directory.nau.edu/
person/by96
Received by the editors: 17.06.2020
and in final form 24.02.2021.
mailto:sudipta.mallik@nau.edu
http://oak.ucc.nau.edu/sm2825/
http://oak.ucc.nau.edu/sm2825/
mailto:bahattin.yildiz@nau.edu
profile.directory.nau.edu/person/by96
profile.directory.nau.edu/person/by96
S. Mallik, B. Yildiz
|