Strong conjecture on rooted F-irregular graphs

Let FF be a connected graph of order F3|F|\geq 3, and let rr be a root of FF. A graph GG is (F)r(F)_r-irregular if the rooted copies of FF with root corresponding to each vertex of GG occur in pairwise distinct numbers. The graph K1,n1K_{1,n-1} is the star on nn vertices, and its center is its unique vertex of degree n1n-1.

Strong conjecture on rooted FF-irregular graphs. For every connected graph FF of order F3|F| \ge 3 and each root rr of FF, unless F=K1,n1F=K_{1,n-1} and rr is the center of K1,n1K_{1,n-1}, there exist infinitely many (F)r(F)_r-irregular graphs.

The excluded star-center case is impossible: no nontrivial graph is (K1,n1)r(K_{1,n-1})_r-irregular there. The paper proves the corresponding assertion for paths except for the central root of P3P_3, and establishes simultaneous rooted and ordinary path irregularity in the stated families; the general conjecture remains open.

Sources & referencesView supporting material

Primary source

Tatiana Dovzhenok, “From roots to paths: graphs simultaneously irregular with respect to rooted and ordinary paths”, arXiv:2607.11700 (2026).

Additional references

3 papers in this index state this conjecture (2025–2026). The statement above is taken from the most recent of them; the others are arXiv:2602.23227, arXiv:2512.05487.

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.