(≤ k)-hereditarily Reconstructible Digraphs
Nadia El Amri
For a vertex subset X of a digraph D, we denote by D[X] the subdigraph of D induced on X. Given a nonnegative integer k, two digraphs D, D′defined on the same vertex set V are (≤ k)-hypomorphic if for every subset X of V with at most k elements, the subdigraphs D[X] and D′[X] are isomorphic. A digraph D′ is hereditarily isomorphic to D, if for every subset X of V, the subdigraphs D[X] and D′[X] are isomorphic. A digraph D is (≤ k)-hereditarily reconstructible, whenever each digraph D′(≤ k)-hypomorphic to D, is hereditarily isomorphic to it. In this paper we characterize for each nonnegative integer k, the (≤ k)-hereditarily reconstructible digraphs.
Keywords: Digraph, isomorphy, hereditary isomorphy, hereditary reconstructibility
Mathematics Subject Classification: 05C20, 05C60