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

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)|\ge 2$, there exist infinitely many $F$-irregular graphs. Conversely, if $|E(F)|\le 1$, we show that no non-trivial $F$-irregular graph exists.

arXiv comment13 pages, 4 figures