Every tournament $T$ of order at least 3 admits infinitely many $T$-irregular oriented graphs
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 \ge 3$, there exists an infinite family of $T$-irregular oriented graphs. Our proof is constructive. For $n \ge 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.
Authors
- Tatiana Dovzhenok
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-02
- DOI
- https://doi.org/10.48550/arxiv.2611.02760
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint