On $\overrightarrow{C_n}$-irregular oriented graphs

Abstract

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 $\overrightarrow{C_n}$-irregular graphs, where $\overrightarrow{C_n}$ is an oriented cycle of order $n$ (a strongly connected oriented graph that is formed from a simple undirected cycle $C_n$ on $n$ vertices by orienting each of its edges). For every integer $n\ge 3$, we prove that there exists an infinite family of $\overrightarrow{C_n}$-irregular graphs. In addition, we show that the order of a non-trivial $\overrightarrow{C_3}$-irregular graph can be any integer not less than $10$ and no others. We also construct $\overrightarrow{C_4}$-irregular graphs of any order at least $7$ and prove that there are no non-trivial $\overrightarrow{C_4}$-irregular graphs of order less than $7$.

Published online. 18 pages, 11 figures