Two $\{ 4,n-3\}$-isomorphic $n$-vertex digraphs are hereditarily isomorphic

Abstract

Let $D$ and $D^{'}$ be two digraphs with the same vertex set $V$, and let $F$ be a set of positive integers. The digraphs $D$ and $D^{'}$ are \emph{hereditarily isomorphic} whenever the (induced) subdigraphs $D[X]$ and $ D^{'}[X]$ are isomorphic for each
nonempty vertex subset $X$. They are $F$\emph{-isomorphic} if the subdigraphs $D[X]$ and $ D^{'}[X]$ are isomorphic for each vertex subset $X$ with $ \mid X\mid \in F$.

In this paper, we prove that if $D$ and $D^{'}$ are two $\{4,n-3\}$-isomorphic $n$-vertex digraphs, where $n \geq 9$, then $D$ and $D^{'}$ are hereditarily isomorphic. As a corollary, we obtain that given integers $k$ and $n$ with $4 \leq k \leq n-6$, if $D$ and $D^{'}$ are two $\{ n-k\}$-isomorphic $n$-vertex digraphs, then $D$ and $D^{'}$ are hereditarily isomorphic.