Existence conjecture for non-trivial -irregular graphs
Let be a connected graph of order at least . An -irregular graph is a graph in which no two distinct vertices have isomorphic -neighbourhoods.
Existence conjecture. For every connected graph of order or more, there exists a non-trivial -irregular graph.
The conjecture concerns the existence of irregular graphs relative to an arbitrary connected graph . It is known for stars and complete graphs of order at least , but the general case is not resolved in the supplied text.
References
Primary source
Tatiana Dovzhenok, Ilya Lukashenko and Yahor Filiuta, “On C_n-irregular oriented graphs”, arXiv:2512.05487 (2026).
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
No solutions have been posted yet.