On $\overrightarrow{C_{n}}$-irregular oriented graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914586379157504 |
|---|---|
| author | Dovzhenok, Tatiana Lukashenko, Ilya Filiuta, Yahor |
| author_facet | Dovzhenok, Tatiana Lukashenko, Ilya Filiuta, Yahor |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_05487 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On $\overrightarrow{C_{n}}$-irregular oriented graphs Dovzhenok, Tatiana Lukashenko, Ilya Filiuta, Yahor Combinatorics 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$. |
| title | On $\overrightarrow{C_{n}}$-irregular oriented graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.05487 |