MVLSC HomeΒ β€’Β Issue Contents

The Hereditary-Half-Reconstructibility of Digraphs
Moncef Bouaziz and Nadia El Amri

Let 𝐺 := (𝑉, 𝐸) be a digraph. The subdigraph of 𝐺 induced by a subset 𝑋 of 𝑉 is denoted by 𝐺[𝑋]. The dual of 𝐺, denoted by 𝐺*, is the digraph obtained from 𝐺 by reversing all its arcs. A digraph 𝐺′ := (𝑉′, 𝐸′) is hemimorphic to 𝐺 if 𝐺 and 𝐺′ are isomorphic or 𝐺* and 𝐺′ are isomorphic. Given a nonnegative integer π‘˜, a digraph 𝐺′ defined on 𝑉 is (≀ π‘˜)-hemimorphic to 𝐺 if for every subset 𝑋 of 𝑉 with at most π‘˜ elements, the subdigraphs 𝐺[𝑋] and 𝐺′[𝑋] are hemimorphic. A digraph 𝐺′ defined on 𝑉 is hereditarily hemimorphic to 𝐺, if for every subset 𝑋 of 𝑉, the subdigraphs 𝐺[𝑋] and 𝐺′[𝑋] are hemimorphic. The digraph 𝐺 is (≀ π‘˜)-hereditarily-half reconstructible, whenever each digraph 𝐺′ (≀ π‘˜)-hemimorphic to 𝐺, is hereditarily hemimorphic to it. In this paper we answer Y. Boudabbous’s question by characterizing the (≀ π‘˜)-hereditarily half-reconstructible digraphs, for each integer π‘˜ such that π‘˜ β‰₯ 7.

Keywords: Digraph, isomorphy, module, difference class, dual, reconstruction, hereditary hemimorphy

Mathematics Subject Classification: 05C20, 05C60

Full Text (IP)