Existence threshold conjecture for regular link-irregular graphs
Existence threshold conjecture for regular link-irregular graphs
Let be a graph on vertices. It is link-irregular if and are non-isomorphic for every pair of distinct vertices , where denotes the neighborhood of and 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 vertices if and only if . The paper establishes that no regular link-irregular graph exists for , extending earlier nonexistence results for regularities . The conjectured threshold at 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.