2025/12/05 by Dovzhenok, Tatiana, Lukashenko, Ilya, Filiuta, Yahor
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.05487
Let F and G be simple finite oriented graphs (without symmetric arcs). A graph G is called F-irregular if any two distinct vertices in G belong to a different number of subgraphs of G isomorphic to F. In this paper, we investigate the problem of the existence of \overrightarrowCn-irregular graphs, where \overrightarrowCn is an oriented circle of order n (a strongly connected oriented graph that is formed from a simple undirected cycle Cn on n vertices by orienting each of its edges). For every integer n ≥ 3, we prove that there exists an infinite family of \overrightarrowCn-irregular graphs. In addition, we show that the order of a non-trivial \overrightarrowC3-irregular graph can be any integer not less than 10 and nothing else. We also construct \overrightarrowC4-irregular graphs of any order starting from 7 and prove that there is no non-trivial \overrightarrowC4-irregular graph of order less than 7.