Existence threshold conjecture for regular link-irregular graphs

Let GG be a graph on nn vertices. It is link-irregular if G[N(u)]G[N(u)] and G[N(v)]G[N(v)] are non-isomorphic for every pair of distinct vertices u,vu,v, where N(u)N(u) denotes the neighborhood of uu and G[N(u)]G[N(u)] the subgraph induced by that neighborhood. A graph is regular if all vertices have the same degree. Existence threshold conjecture. There exists a regular link-irregular graph on nn vertices if and only if n12n\geq 12. The paper establishes that no regular link-irregular graph exists for n9n\leq 9, extending earlier nonexistence results for regularities 0,1,2,3,40,1,2,3,4. The conjectured threshold at 1212 remains open.

Sources & referencesView supporting material

Primary source

Alexander Bastien and Omid Khormali, “On the Regularity, Planarity and Edge Bounds of Link-irregular Graphs”, arXiv:2503.21916 (2025).

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.