← All problems

Strong conjecture on F-irregular oriented graphs

For every weakly connected oriented graph FF with ∣V(F)∣≥3|V(F)|\ge 3, there exist infinitely many oriented graphs GG such that, for every pair of distinct vertices u,v∈V(G)u,v\in V(G), ∣{H⊆G:H≅F, u∈V(H)}∣≠∣{H⊆G:H≅F, v∈V(H)}∣\left|\{H\subseteq G:H\cong F,\ u\in V(H)\}\right|\ne\left|\{H\subseteq G:H\cong F,\ v\in V(H)\}\right|.

References

Progress summary

Refreshed
Open · progress reported

A new construction handles every tournament, but the broader claim for all weakly connected oriented graphs remains open.

The strong conjecture predicts infinitely many FF-irregular oriented graphs for every weakly connected oriented graph FF with at least three vertices. The newly reported result addresses all tournaments but does not settle the full conjecture.

Known results

  • Dovzhenok, Lukashenko, and Filiuta proved the conjecture for every oriented cycle Cn→\overrightarrow{C_n}.
  • Their work gives exact smallest orders for non-trivial C3→\overrightarrow{C_3}- and C4→\overrightarrow{C_4}-irregular oriented graphs: 1010 and 77, respectively.

November 2, 2026: tournament case

Tatiana Dovzhenok reports that every tournament of order at least 33 admits infinitely many irregular oriented graphs, using vertex cloning for tournaments of order at least 44. This is claimed as a constructive settlement of the tournament case, while arbitrary weakly connected oriented graphs remain untreated.

Current status (as of November 2026): The tournament case and the oriented-cycle case are claimed results, but the strong conjecture for all weakly connected oriented graphs remains open.

Sources

Solutions 0

No solutions have been posted yet.