Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

On the existence of F-irregular graphs for disconnected graphs F

  • Tatiana Dovzhenok
Open at sourcePDFDOICite

Abstract

For a given graph F, a graph G is F-irregular if all its vertices have pairwise distinct F-degrees, where the F-degree of a vertex v is the number of subgraphs of G containing v and isomorphic to F. While the existence of F-irregular graphs has been actively studied for connected graphs F, the case where F is disconnected remains entirely unexplored. In this paper, we provide a complete solution to this problem. We prove that for every disconnected graph F with |E(F)| ≥ 2, there exist infinitely many F-irregular graphs. Conversely, if |E(F)| ≤ 1, we show that no non-trivial F-irregular graph exists.

Related

  1. Quasi-isometries between graphs of totally disconnected locally compact groups
    Sebastian Giersbach
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. Disconnected graphs and extremal bounds for realizable distance orders
    Gerardo L. Maldonado, Leonardo Martínez-Sandoval, Miguel Raggi +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A short note on Kn-irregular graphs
    Tatiana Dovzhenok
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On infinite families of [Pn]-irregular graphs
    Tatiana Dovzhenok, Ilya Lukashenko, Andrei Mikhalev +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A Complete Proof of the Strong Conjecture about F-Irregular Graphs
    Tatiana Dovzhenok, Artem Filuta
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dovzhenok2026existence,
  title = {{On the existence of $F$-irregular graphs for disconnected graphs $F$}},
  author = {Tatiana Dovzhenok},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.18349},
  eprint = {2610.18349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18349},
}
RIS
TY  - UNPB
TI  - On the existence of F-irregular graphs for disconnected graphs F
AU  - Tatiana Dovzhenok
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.18349
UR  - https://arxiv.org/abs/2610.18349
AB  - For a given graph F, a graph G is F-irregular if all its vertices have pairwise distinct F-degrees, where the F-degree of a vertex v is the number of subgraphs of G containing v and isomorphic to F. While the existence of F-irregular graphs has been actively studied for connected graphs F, the case where F is disconnected remains entirely unexplored. In this paper, we provide a complete solution to this problem. We prove that for every disconnected graph F with |E(F)| ≥ 2, there exist infinitely many F-irregular graphs. Conversely, if |E(F)| ≤ 1, we show that no non-trivial F-irregular graph exists.
ER  -