The conjecture on existence of F-irregular graphs

Let FF and GG be graphs. The FF-degree of a vertex vv in GG is the number of subgraphs of GG isomorphic to FF that contain vv. A graph GG is FF-irregular if any two distinct vertices of GG have different FF-degrees.

Existence conjecture. For every connected graph FF on three or more vertices, there exists an FF-irregular graph.

The conjecture generalizes the known existence results for complete graphs and stars. It was later strengthened by the assertion that infinitely many such graphs exist for every connected graph FF of order at least 33; the general conjecture is solved here only for the class of graphs FF of diameter 22.

Sources & referencesView supporting material

Primary source

Tatiana Dovzhenok, “Proof of the strong conjecture about F-irregular graphs in the class of graphs \F\ of diameter 2”, arXiv:2602.23227 (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.