Paperlane

no. 7 · Tuesday 3 November 2026

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

Tatiana Dovzhenok

math.CO

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 \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.

fields
Combinatorics
pdf ↗ page arXiv:2611.02760 ↗