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


Youssef Boudabbous




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 D 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. To the memory of my dear master Gérard LOPEZ who taught me and gave me the passion of reconstruction. With all my gratitude and admiration,