Every tournament T of order at least 3 admits infinitely many T-irregular oriented graphs

Abstract

Let F be a fixed graph. A graph G is F-irregular if any two distinct vertices of G belong to a different number of subgraphs of G isomorphic to F. In this paper, we settle the strong conjecture about F-irregular oriented graphs (Dovzhenok, Lukashenko, and Filiuta, 2026) for the case of tournaments. Specifically, we prove that for every tournament T of order n ≥ 3, there exists an infinite family of T-irregular oriented graphs. Our proof is constructive. For n ≥ 4, it is based on the vertex cloning method, and the underlying graphs of the constructed T-irregular oriented graphs are inherently K_n-irregular.

Oriented Paths with Few Direction Flips Are Tournament Anti-Sidorenko
Hao Chen, Yupeng Lin
arXiv13 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Infinitely many normalized solutions of L²-supercritical NLS equations on noncompact metric graphs with localized nonlinearities
Pablo Carrillo, Damien Galant, Louis Jeanjean +1
Discrete and Continuous Dynamical Systems - Series A8 Oct 2026Peer-reviewedCC BY 4.0Full text2 citedAnalysis & PDEsHAL
On the existence of F-irregular graphs for disconnected graphs F
Tatiana Dovzhenok
arXiv13 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A short note on K_n-irregular graphs
Tatiana Dovzhenok
arXiv24 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On infinite families of [P_n]-irregular graphs
Tatiana Dovzhenok, Ilya Lukashenko, Andrei Mikhalev +1
arXiv21 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{dovzhenok2026every,
  title = {{Every tournament $T$ of order at least 3 admits infinitely many $T$-irregular oriented graphs}},
  author = {Tatiana Dovzhenok},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.02760},
  eprint = {2611.02760},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02760},
}

RIS

TY  - UNPB
TI  - Every tournament T of order at least 3 admits infinitely many T-irregular oriented graphs
AU  - Tatiana Dovzhenok
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.02760
UR  - https://arxiv.org/abs/2611.02760
AB  - Let F be a fixed graph. A graph G is F-irregular if any two distinct vertices of G belong to a different number of subgraphs of G isomorphic to F. In this paper, we settle the strong conjecture about F-irregular oriented graphs (Dovzhenok, Lukashenko, and Filiuta, 2026) for the case of tournaments. Specifically, we prove that for every tournament T of order n ≥ 3, there exists an infinite family of T-irregular oriented graphs. Our proof is constructive. For n ≥ 4, it is based on the vertex cloning method, and the underlying graphs of the constructed T-irregular oriented graphs are inherently K_n-irregular.
ER  -

Abstract

Related

Cite