PreprintarXiv licencearXiv
A Complete Proof of the Strong Conjecture about F-Irregular Graphs
Abstract
A graph G is called F-irregular if all its vertices have distinct F-degrees, defined as the number of subgraphs of G isomorphic to a given graph F and containing the respective vertex. We prove the Strong Conjecture about F-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every connected graph F of order at least three, there exist infinitely many F-irregular graphs. Fundamentally generalizing the classical existence conjecture by Chartrand et al. (1987), this work presents an authorized English translation of our original February 2024 manuscript, which was publicly presented in full at two scientific conferences the same year.
Related
- Strong complete immersions in graphs with independence number two
- A proof of the strong Erdős--Frankl--Füredi cover-free conjecture
- A Proof of McLeod's 1959 Conjecture on Complete Homogeneous Symmetric Ratios
- Proof of the Göbel-Veldman conjecture on diametrical graphs
- A proof of the strong Gaussian product inequality conjecture
BibTeX
@misc{dovzhenok2026complete,
title = {{A Complete Proof of the Strong Conjecture about $F$-Irregular Graphs}},
author = {Tatiana Dovzhenok and Artem Filuta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19245},
eprint = {2609.19245},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19245},
}
RIS
TY - UNPB
TI - A Complete Proof of the Strong Conjecture about F-Irregular Graphs
AU - Tatiana Dovzhenok
AU - Artem Filuta
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19245
UR - https://arxiv.org/abs/2609.19245
AB - A graph G is called F-irregular if all its vertices have distinct F-degrees, defined as the number of subgraphs of G isomorphic to a given graph F and containing the respective vertex. We prove the Strong Conjecture about F-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every connected graph F of order at least three, there exist infinitely many F-irregular graphs. Fundamentally generalizing the classical existence conjecture by Chartrand et al. (1987), this work presents an authorized English translation of our original February 2024 manuscript, which was publicly presented in full at two scientific conferences the same year.
ER -