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 hereditarily isomorphic whenever the (induced) subdigraphs D[X] and D'[X] are isomorphic for each nonempty vertex subset X. They are F-isomorphic if the subdigraphs D[X] and D'[X] are isomorphic for each vertex subset X with |X|€ F. In this paper, we prove that if D and D' are two {4,n-3}-isomorphic n-vertex digraphs, where n >= 9, then D and D0 are hereditarily isomorphic. As a corollary, we obtain that given integers k and n with 4 <= k <= n-6, if D and D' are two {n-k}-isomorphic n-vertex digraphs, then D and D' are hereditarily isomorphic.
nema