The conjecture on existence of F-irregular graphs
The conjecture on existence of F-irregular graphs
Let and be graphs. The -degree of a vertex in is the number of subgraphs of isomorphic to that contain . A graph is -irregular if any two distinct vertices of have different -degrees.
Existence conjecture. For every connected graph on three or more vertices, there exists an -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 of order at least ; the general conjecture is solved here only for the class of graphs of diameter .
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
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.