The von Neumann neighborhood conjecture for graph codes

About 7 years old · traced to

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 [In∣A][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 S∩von⁡(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.

References

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.