Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
arXiv:2609.01474v3 Announce Type: replace Abstract: Codes over graphs store symbols on edges of a complete undirected graph on $n$ vertices with a self-loop at each vertex; erasing a node removes all its incident edges. Extending Yohananov, Efron, and Yaakobi's construction, we obtain binary codes correcting any three node erasures at infinitely many prime lengths $n$, unconditionally, with redundancy $3n-2$, one bit above the graph Singleton bound. The earlier construction has the same redundancy but requires $2$ to be primitive modulo $n$, which is not known for infinitely many primes. We give a deterministic decoder for these triple-node codes using $O(n^2)$ binary operations and construct Singleton-optimal binary triple-node codes at $n=6,8,10,12$. When $2$ is primitive modulo an odd prime $n$, we extend their double- and triple-node codes to binary codes correcting $\rho$ node erasures with redundancy $\rho n-(\rho-1)$ for $2\leq\rho\leq(n+1)/2$, saving $\rho-1$ bits over the binary symmetric rank-metric construction when $\rho