Hulls of codes from incidence matrices of connected regular graphs

D. Ghinelli, J. D. Key, Thomas McDonough

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
155 Downloads (Pure)


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 (nk, λ, μ), 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.
Original languageEnglish
Pages (from-to)35-54
JournalDesigns, Codes and Cryptography
Issue number1
Early online date25 Mar 2012
Publication statusPublished - Jan 2014


  • Incidence matrix
  • Graph
  • Code
  • Hull
  • Permutation decoding
  • 05B05
  • 05C38
  • 94B05


Dive into the research topics of 'Hulls of codes from incidence matrices of connected regular graphs'. Together they form a unique fingerprint.

Cite this