First Online 2026
UDC 519.17
MSC: 05C07, 05C20, 05C35, 05C38
https://doi.org/10.21538/0134-4889-2026-32-4-fon-01
Full Text
T.S. Dovzhenok, I.D. Lukashenko, Y.V. Filiuta. On $\overrightarrow{C_{n}}$-irregular oriented graphs.
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$.
Keywords: strong conjecture about $F$-irregular oriented graphs, oriented cycle on $n$ vertices $\big(\overrightarrow{C_n}\big)$, $\overrightarrow{C_n}$-degree of a vertex, $\overrightarrow{C_n}$-irregular graph
REFERENCES
1. Chartrand G., Holbert K.S., Oellermann O.R., Swart H.C. F-degrees in graphs. Ars Comb., 1987, vol. 24, pp. 133–148.
2. Behzad M., Chartrand G. No graph is perfect. Amer. Math. Monthly, 1967, vol. 74, pp. 962–963. https://doi.org/10.2307/2315277
3. Ali A., Chartrand G., Zhang P. Irregularity in graphs. NY, Springer, 2021, 109 p.
https://doi.org/10.1007/978-3-030-67993-4
4. Salehi E. On P3-degree of graphs. J. Comb. Math. Comb. Comput., 2007, vol. 62, pp. 45–51.
5. Berikkyzy Z., Bjorkman B., Blake H.S., Jahanbekam S., Keough L., Moss K., Rorabaugh D., Shan S. Triangle-degree and triangle-distinct graphs. Discrete Math., 2024, vol. 347, art. no. 113695. https://doi.org/10.1016/j.disc.2023.113695
6. Dovzhenok T.S., Filuta A.V., Chuhai N.E. On some results of the study of F-irregular graphs in the class of biconnected graphs F. J. Belarusian State Univ. Mathematics and Informatics, 2024, no. 2, pp. 54–64 (in Russian).
7. Dovzhenok T.S. Proof of the F-irregular graph conjecture for the path $P_n.$ Problems of Physics Mathematics and Technics, 2026, № 1 (66), pp. 53–58.
Received January 19, 2026
Revised April 22, 2026
Accepted April 27, 2026
Published online May 12, 2026
Tatiana Stepanovna Dovzhenok, Cand. Sci. (Phys.-Math.), Research laboratory “Mathematics of hybrid intelligence systems”, Francisk Skorina Gomel State University, Gomel, 246028 Belarus,
e-mail: t.dovzhenok@mail.ru
Ilya Denisovich Lukashenko, Research laboratory “Algebra and geometry of complex systems”, Francisk Skorina Gomel State University, Gomel, 246028 Belarus, e-mail: i.d.lukashenko@gmail.com
Yahor Vitalyevich Filiuta, Research laboratory “Algebra and geometry of complex systems” Francisk Skorina Gomel State University, Gomel, 246028 Belarus, e-mail: yahorfiliuta@gmail.com
Cite this article as: T.S. Dovzhenok, I.D. Lukashenko, Y.V. Filiuta. On $\overrightarrow{C_{n}}$-irregular oriented graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026. https://doi.org/10.21538/0134-4889-2026-32-4-fon-01
На русском
Т.С. Довженок, И.Д. Лукашенко, Е.В. Филюта. О $\overrightarrow{C_{n}}$-иррегулярных ориентированных графах.
Пусть $F$ и $G$ – простые конечные ориентированные графы (без симметричных дуг). Граф $G$ называется
$F$-иррегулярным, если любые две различные вершины графа $G$ принадлежат различному числу подграфов из $G$, изоморфных графу $F$. В этой статье мы исследуем проблему существования $\overrightarrow{C_n}$-иррегулярных графов, где $\overrightarrow{C_n}$ – ориентированный цикл порядка $n$ (сильно связный ориентированный граф, образованный из простого неориентированного цикла $C_n$ на $n$ вершинах путем ориентации каждого из его ребер). Для каждого целого числа $n \ge 3$ мы доказываем, что существует бесконечное семейство
$\overrightarrow{C_n}$-иррегулярных графов. Кроме того, мы показываем, что порядок нетривиального $\overrightarrow{C_3}$-иррегулярного графа может быть любым целым числом не меньше $10$ и только им. Мы также строим $\overrightarrow{C_4}$-иррегулярные графы любого порядка начиная с $7$, и доказываем, что не существует нетривиальных $\overrightarrow{C_4}$-иррегулярных графов порядка меньше $7$.
Ключевые слова: сильная гипотеза об $F$-иррегулярных ориентированных графах, ориентированный цикл на $n$ вершинах $\big(\overrightarrow{C_n}\big)$, $\overrightarrow{C_n}$-степень вершины, $\overrightarrow{C_n}$-иррегулярный граф
