Lowest density MDS array codes on incomplete graphs

In this paper we introduce the concept of lowest density MDS array codes on incomplete graphs. Array codes are used to protect against erasures by adding redundancy. Application examples are networks of wireless sensors or smart meters, where nodes can exchange data between themselves and store parity information for protection against multiple node failures. Array codes can ensure that the data generated by the whole network can be reconstructed when only a subset of nodes are accessible. However, conventional array codes assume that all nodes can communicate with one another to exchange information; in a practical network, some nodes may not be connected between them. Such a network can be described by an incomplete graph and in this paper we discuss the conditions on the minimum node degree that allow lowest density MDS array codes to exist on such graphs. We also present an explicit design for network configurations with minimum node degree. The code is capable of correcting up to two erased nodes for any incomplete graph with an even number of nodes. It can also recover any r node failures for one nonisomorphic class of regular incomplete graphs with a number of nodes that is multiple of r.