REVIEW 2 major objections 4 minor 15 references
Isodual and Self-dual Codes from Graphs
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For any simple graph, the binary code generated by [I_n|A] has minimum distance equal to the smallest value of |S|+|von(S)| over nonempty vertex subsets S.
desk verdict The paper's main distance formula and self-duality characterizations are correct and worth knowing; the join section contains a false theorem that needs fixing before this can be accepted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The odd-neighborhood operator von(S) = {v : |N(v) intersect S| is odd} on the vertex set of Gamma, together with the binary adjacency matrix A. It carries the argument because a sum of columns of A has ones exactly on von(S); therefore the minimal linear dependencies of [A|I_n] are in bijection with pairs (S, von(S)). This yields the minimum-distance formula and, through the symmetry A = A^T, the isoduality and self-duality criteria.
What would settle it
Enumerate all simple graphs on, say, six vertices, compute the code generated by [I_6|A], and compare its brute-force minimum distance with min over nonempty S of (|S|+|von(S)|); any mismatch would disprove Theorem 2.9. Alternatively, search for a graph with $A^{2}$ congruent to I_n mod 2 whose code contains a codeword of weight not divisible by 4, which would contradict Theorem 3.3.
Extended reading notes
Core claim
The central discovery is a dictionary between a code C with generator [I_n|A] and the graph Gamma whose adjacency matrix is A. Theorem 2.9 states that d(C) = min over nonempty S of V of (|S| + |von(S)|), where von(S) is the odd-neighborhood of S. The proof identifies minimally dependent columns of the parity-check matrix [A|I_n] with unions of columns indexed by S and by von(S). Theorem 3.1 then characterizes self-duality of C by $A^{2}$ being congruent to I_n mod 2, equivalently all vertices have odd degree and all pairs of distinct vertices have an even number of common neighbors; Theorem 3.3 adds that the code is Type II exactly when all degrees are 3 mod 4. The paper applies these conditions to complete graphs, strongly regular graphs, and joins, producing families of self-dual, Type I and Type II codes with known parameters.
Load-bearing premise
The argument assumes A is the symmetric adjacency matrix of a simple undirected graph, so that the parity-check matrix is [A|I_n]; for directed or asymmetric adjacency, the isodual structure and the von(S) formula would need separate treatment.
Editorial extensions
If this is right
- Every graph isomorphism class yields a code whose minimum distance is a graph invariant under the formula, even when the codes themselves are not identical.
- Any graph with all degrees odd and pairwise even common-neighbor counts produces a self-dual [2n,n] code, and if degrees are 3 mod 4 the code is doubly even.
- Complete graphs K_n with n even give self-dual [2n,n,4] codes; K_4 and K_8 give extremal Type II codes and K_6 an extremal Type I code.
- The join of two graphs whose codes are self-dual is again self-dual, with type rules depending on the sizes modulo 4.
- For any graph, d(C) is at most rk2(A)+1, giving a lower bound on the 2-rank of a graph.
Reading between the lines
- If the minimum-distance formula is correct, it gives an efficient combinatorial way to compute or bound the distance of [I_n|A] codes without enumerating codewords, since it reduces the computation to a search over 2^n vertex subsets.
- The same von(S) operator may transfer to other graph-derived matrices, such as incidence matrices or signed adjacency matrices, by replacing 'odd neighborhood' with the appropriate parity condition; the paper does not explore those settings.
- The paper's Conjecture 2.16, that a minimizing set S satisfies S = von(S) or S intersect von(S) is empty, could be tested exhaustively on all graphs up to seven or eight vertices; if true it would simplify the search for minimum-weight codewords.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies binary linear codes generated by matrices of the form [I_n | A], where A is the adjacency matrix of a simple graph on n vertices. The main results are a combinatorial formula for the minimum distance of such codes in terms of odd-neighborhood sets (Theorem 2.9), necessary and sufficient conditions for self-duality and Type I/II status in terms of graph degrees and common-neighbor parities (Theorems 3.1, 3.3, 3.8), applications to complete graphs and strongly regular graphs, and a final section analyzing the effect of the join operation on minimum distance and self-duality.
Significance. If the main results hold, the paper provides a clean dictionary between graph-theoretic quantities and code parameters: minimum distance becomes an extremal problem over subsets S involving |S|+|von(S)|, and self-duality is exactly the condition A^2 = I_n over F_2. Theorems 2.9, 3.1, 3.3, and 3.8 are derived carefully from standard parity-check theory and appear correct. However, the join section contains a false theorem (Theorem 3.12(b)) with an erroneous proof, so the paper is not yet acceptable in its current form.
major comments (2)
- [Section 3, Theorem 3.12(b) and its proof] Theorem 3.12(b) is false as stated. A concrete counterexample is given by taking Γ1 = K1 and Γ2 the 5-vertex graph with edges 12, 13, 14, 25, 34, 45. For Γ2, one computes d2 = 3 via Theorem 2.9 (e.g., S = {2} gives |S|+|von(S)| = 3 and no subset gives less), while d1 = 1. In the join Γ1 ∨ Γ2, the subset S = {c,1,2} (where c is the center of K1) has |S| = 3 and von(S) = ∅, because the pair {1,2} satisfies von2({1,2}) = V2 and the center contributes even adjacency. Since the join has no isolated vertices and no duplicate vertices, d = 3. Thus d1 + d2 = 4 > 3 = d, contradicting the claimed inequality d1 + d2 ≤ d. The error in the proof occurs in Case 2, where the authors assert that von(S) is the union of V2 and von1(S1). The correct formula for |S1| odd and |S2| even is von(S) = von1(S1) ∪ (V2 \ von2(S2)), because a vertex w in V2 sees |S1| odd neighbors in S1 and has odd adjacency to S2 exactly when w ∈ von2(S2); the total parity is odd exactly when w ∉ von2(S2). The proof uses the larger set, invalidating the inequality. The theorem should be corrected or its statement revised to a true lower bound using the correct von(S) expression.
- [Section 3, Theorem 3.11(c)] The statement of Theorem 3.11(c) says that when exactly one of n1 and n2 is divisible by 4, C([I_{n1+n2}|A]) is Type I. The proof argues that n1+n2 ≡ 2 (mod 4) and hence the code length is 2(n1+n2) ≡ 4 (mod 8), which is not a multiple of 8, so the code cannot be Type II. This argument is correct, but it assumes the code is self-dual; if the preconditions of the theorem are not explicitly stated, the reader may be confused. Please state explicitly that (c) concerns codes that are already known to be self-dual from Theorem 3.10, or add the self-duality condition to the theorem statement.
minor comments (4)
- [Abstract and page 1] The abstract and first page contain several OCR-style typos: 'in particu lar', 'a dding', 'have made it suitable', 'needed throughout' should be cleaned up. The sentence 'we can bring the generator matrix G into a standard form [I_k|A]' silently assumes Gaussian elimination over F_2; this is standard but could be said explicitly.
- [Theorem 2.8 proof] In the proof of Theorem 2.8, Case 2, the equation 'A1 + A2 + · · · + Ak + ei2 + · · · + eid−k ≡ 0 (mod 2)' appears to contain a typo: the term ei1 is missing on the left-hand side. It should read 'A1 + A2 + · · · + Ak + ei1 + ei2 + · · · + eid−k ≡ 0 (mod 2)' for the subsequent conclusion to hold.
- [Observation 2.15 and Conjecture 2.16] Observation 2.15 is phrased as a remark about an apparent pattern; if the authors intend the observation to support Conjecture 2.16, they should either prove it for the listed cases or label it as an empirical observation. The phrase 'At least one of these two properties seems to hold' is informal for a research paper.
- [References] Reference [15] is cited for the [I_n|A] construction, but the connection to isoduality in the introduction (item 3) is not attributed. It would improve the exposition to state explicitly where the isoduality observation comes from, whether from the present paper or from previous work.
Circularity Check
No significant circularity: all main results are derived from definitions via self-contained linear algebra.
full rationale
The paper's central claims are the minimum-distance formula (Theorem 2.9) and the self-duality and type conditions (Theorems 3.1 and 3.3). Theorem 2.9 is proven from Theorem 2.8, which is derived by direct column-sum arguments on the parity-check matrix [A|I_n]; there are no fitted parameters, no predictions from a fitted subset, and no dependence on the authors' own prior results that would force a conclusion. The self-dual condition A^2 = I_n follows from the standard row-orthogonality of [I_n|A], and Theorem 3.3 is proved by an induction using Lemma 3.2, all self-contained. The construction [I_n|A] is explicitly credited to Tonchev [15], an external source, and the only self-citation (Mallik and Shader [11]) concerns prior studies of column dependencies; the actual theorem used (Theorem 2.6) is proved in the paper itself, so the citation is not load-bearing. The paper contains no renaming of known empirical patterns as organization, no ansatz smuggled in via self-citation, and no uniqueness theorem imported from the authors' own prior work. The alleged falsehood in Theorem 3.12(b) is a correctness concern rather than a circularity concern, and per the review rules it does not affect the circularity score.
Assumptions & free parameters
assumptions (4)
- standard math Minimum distance of a linear code equals the smallest number of linearly dependent columns of a parity-check matrix.
- standard math For a code with generator [I_k|A], a parity-check matrix is [-A^T|I_{n-k}], which over F2 with symmetric A becomes [A|I_n].
- standard math Every graph has an even number of odd-degree vertices.
- standard math Rains shadow bound on extremal self-dual codes.
Cite this review
Pith. "Pith review of Isodual and Self-dual Codes from Graphs." pith.science (2026). https://pith.science/paper/ZUQCOUCL
@misc{pith2026190803513,
author = {Pith},
title = {Pith review of: Isodual and Self-dual Codes from Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZUQCOUCL}},
note = {Machine review of arXiv:1908.03513}
}
abstract
Binary linear codes are constructed from graphs, in particular, by the generator matrix $[I_n|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.
Reference graph
Works this paper leans on
-
[1]
Switched symplectic graphs and their 2 -ranks
A. Abiad, W. H. Haemers, “Switched symplectic graphs and their 2 -ranks”, Des. Codes Crypt., vol. 81, no. 1, pp. 35–41, 2016
work page 2016
-
[2]
D. Crnkovi´ c, B.G. Rodrigues, S. Rukavina and L. Simˇ ci´ c, “Te rnary 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
work page 2012
-
[3]
Self-orthogonal codes from the strongly regular graphs on up to 40 vertices
D. Crnkovi´ c, M. Maximovi´ c, 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. 12
work page 2016
-
[4]
A Characterizatio n of Graphs by Codes from their Incidence Matrices
P. Dankelmann, J.D. Key and B. G. Rodrigues, “A Characterizatio n of Graphs by Codes from their Incidence Matrices”, Elect. J. Combinatorics , vol. 20, no. 3, P18, 2013
work page 2013
-
[5]
Binary codes from the comple ments of the tri- angular graphs
W. Fish, R. Fray and E. Mwambene, “Binary codes from the comple ments of the tri- angular graphs”, Quaestiones Mathematicae, vol. 33, no. 4, pp. 399–408, 2010
work page 2010
-
[6]
G. D. Forney, “Codes on Graphs: Fundamentals”, arXiv:1306.62 64
-
[7]
Chromatic Number and the 2-Rank o f a Graph
C. D. Godsil and G. F. Royle, “Chromatic Number and the 2-Rank o f a Graph ”, J. Comb. Series B , vol. 81, pp. 142–149, 2001
work page 2001
-
[8]
New self-dual additive F4-codes constructed from circulant graphs
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
work page 2017
Show all 15 references
-
[9]
LCD codes from adjacency matrice s of graphs
J.D. Key and B.G. Rodrigues, “LCD codes from adjacency matrice s of graphs”, Appl. Alg. Eng. Comm. Comp. , vol. 29, no. 3, pp.227–244, 2018
2018
-
[10]
Codes from graphs related to the categorical prod- uct of triangular graphs and Kn
K. Kumwenda and E. Mwambene, “Codes from graphs related to the categorical prod- uct of triangular graphs and Kn”, IEEE Trans. Inform. Theory Workshop , ITW 2010 Dublin
2010
-
[11]
Classes of graphs with minimum skew ra nk 4
S. Mallik and B. L. Shader, “Classes of graphs with minimum skew ra nk 4”, Linear Algebra Appl. 439 (2013) 3643–3657
2013
-
[12]
Self-dual Codes and Graphs
H. Oral, “Self-dual Codes and Graphs”, Thesis, Simon Frasier University, 1989
1989
-
[13]
Shadow Bounds for Self Dual Codes
E.M. Rains, “Shadow Bounds for Self Dual Codes”, IEEE Trans. Inf. Theory , vol.44, pp.134–139, 1998
1998
-
[14]
Error-correcting codes from graphs
V. Tonchev, “Error-correcting codes from graphs”, Discrete Math. , vol. 257, no. 2-3, pp.549–557, 2002
2002
-
[15]
Rank-3 Graphs, Block Designs, and Codes with Un equal Symbol Protec- tion
V. Tonchev, “Rank-3 Graphs, Block Designs, and Codes with Un equal Symbol Protec- tion”, Problemy Peredaci Informatsii , vol. 17, no. 2, pp.89–93, 1981. 13
1981
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.