The von Neumann neighborhood conjecture for graph codes

Let AA be the adjacency matrix of a graph Γ\Gamma on nn vertices with vertex set VV. Let CC be the binary linear code generated by [InA][I_n|A], and let d(C)d(C) denote its minimum distance. For a nonempty subset SS of VV, let von(S)\operatorname{von}(S) denote its von Neumann neighborhood. The von Neumann neighborhood conjecture. If

d(C)=S+von(S),d(C)=|S|+|\operatorname{von}(S)|,

then either S=von(S)S=\operatorname{von}(S) or Svon(S)=S\cap\operatorname{von}(S)=\varnothing. The observation preceding this conjecture verifies the claim for complete graphs, while its validity for general graphs is left open.

Sources & referencesView supporting material

Primary source

Sudipta Mallik and Bahattin Yildiz, “Isodual and Self-dual Codes from Graphs”, arXiv:1908.03513 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.