Hulls of codes from incidence matrices of connected regular graphs

Abstract

The hulls of codes from the row span over F_p, for any prime p, of incidence matrices of connected k-regular graphs are examined, and the dimension of the hull is given in terms of the dimension of the row span of A+kI over F_p, where A is an adjacency matrix for the graph. If p = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown in P. Dankelmann, J. D. Key, and B. G. Rodrigues, 'Codes from incidence matrices of graphs', Des. Codes Cryptogr. (To appear, 2012), that the hull is either {0} or has minimum weight at least 2k-2. Here we show that if the graph is strongly regular with parameter set (n,k,lambda,mu), then, unless k is even and mu is odd, the binary hull is non-trivial, of minimum weight generally greater than 2k-2, and we construct words of low weight in the hull; if k is even and mu is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k>2, that has an l-cycle for some l>2, the binary hull is shown to be non-trivial with minimum weight at most 2l(k-2). Properties of the p-ary hulls are also established.