A Fundamental Theorem on Graph Operators

Abstract

A graph operator is a function $\hat{I}“$ defined on some set of graphs such that whenever two graphs $G$ and $H$ are isomorphic, written $G\simeq H$, then $\hat{I}“(G)\simeq \hat{I}“(H)$. For a graph $G$ not in the domain of $\hat{I}“$, we put $\hat{I}“(G)=\varnothing$. Also, let us define $\hat{I}{“}^0(G)=G$, and for any integr $k\ge 1$, $\hat{I}{“}^k(G)=\hat{I}“(\hat{I}{“}^{k-1}(G))$ We prove that if $\hat{I}“$ is a graph operator, then the sequence $⟨\hat{I}{“}^k(G){⟩}_{k=0}^{\infty }$ has only three possible types of behaviour. Either $\hat{I}{“}^k(G)=\varnothing$ for some integer $k>0$, or $\underset{k\to \infty }{\lim }|V(\hat{I}{“}^k(G))|=\infty$, or there exist integers $m\ge 0$, $p>0$ such that the graphs $\hat{I}{“}^j(G)$ are non-isomorphic ($0\le j\le m)$, and $\hat{I}{“}^{n+p}\simeq \hat{I}{“}^n(G)$ for all integers $n\ge m$. We illustrate this using two new graph operators, namely, the path graph operator and the claw graph operator.