TY - JOUR

T1 - Hulls of codes from incidence matrices of connected regular graphs

AU - Ghinelli, D.

AU - Key, J. D.

AU - McDonough, Thomas

N1 - D.Ghinelli, J.D.Key, T.P.McDonough. Hulls of codes from incidence matrices of connected regular graphs. Designs Codes and Cryptography, 2014, vol 70, pg 35-54.

PY - 2014/1

Y1 - 2014/1

N2 - The hulls of codes from the row span over FpFp , 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 FpFp , where A is an adjacency matrix for the graph. Ifp = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown by Dankelmann et al. (Des. Codes Cryptogr. 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, λ, μ), then, unless k is even and μ 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 μ is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k ≥ 3, that has an ℓ-cycle for some ℓ ≥ 3, the binary hull is shown to be non-trivial with minimum weight at most 2ℓ(k−2). Properties of the p-ary hulls are also established.

AB - The hulls of codes from the row span over FpFp , 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 FpFp , where A is an adjacency matrix for the graph. Ifp = 2, for most classes of connected regular graphs with some further form of symmetry, it was shown by Dankelmann et al. (Des. Codes Cryptogr. 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, λ, μ), then, unless k is even and μ 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 μ is odd, we show that the binary hull is zero. Further, if a graph is the line graph of a k-regular graph, k ≥ 3, that has an ℓ-cycle for some ℓ ≥ 3, the binary hull is shown to be non-trivial with minimum weight at most 2ℓ(k−2). Properties of the p-ary hulls are also established.

KW - Incidence matrix

KW - Graph

KW - Code

KW - Hull

KW - Permutation decoding

KW - 05B05

KW - 05C38

KW - 94B05

UR - http://hdl.handle.net/2160/7822

U2 - 10.1007/s10623-012-9635-0

DO - 10.1007/s10623-012-9635-0

M3 - Article

SN - 0925-1022

VL - 70

SP - 35

EP - 54

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

IS - 1

ER -