Existence conjecture for non-trivial FF-irregular graphs

About 1 year old · traced to

Let FF be a connected graph of order at least 33. An FF-irregular graph is a graph in which no two distinct vertices have isomorphic FF-neighbourhoods.

Existence conjecture. For every connected graph FF of order 33 or more, there exists a non-trivial FF-irregular graph.

The conjecture concerns the existence of irregular graphs relative to an arbitrary connected graph FF. It is known for stars and complete graphs of order at least 33, 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

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.