MVLSC Home · Issue Contents · Forthcoming Papers
Description of the Digraphs {−1}-hypomorphic to a Reducible Digraph
Mouna Achour, Youssef Boudabbous and Abderrahim Boussaïri
Let 𝐺 be a digraph with vertex set 𝑉. A module of 𝐺 is a set 𝑀 of vertices indistinguishable by the vertices outside 𝑀. A module of 𝐺 distinct from 𝑉 is a proper module of 𝐺. The digraph 𝐺 is reducible if its vertex set 𝑉 is the union of two proper modules. A digraph 𝐺‘, defined on 𝑉, is {−1}-hypomorphic to 𝐺 whenever the subdigraphs of 𝐺 and 𝐺‘ induced by 𝑉 \ {𝑥} are isomorphic, for every vertex 𝑥. The digraph 𝐺 is {−1}-reconstructible if it is isomorphic to each digraph it is {−1}-hypomorphic to it. In this paper, given a reducible digraph 𝐺 having more than 4 vertices, we describe the digraphs that are {−1}-hypomorphic to 𝐺. Our description is based on the decomposition of Gallai. As an immediate consequence, we obtain that every reducible digraph having more than 4 vertices is {−1}-reconstructible; which improves the {−1}-reconstruction of disconnected graphs obtained by P. J. Kelly in 1957 and that of reducible tournaments obtained by F. Harary and E. Palmer in 1967.
Keywords: Isomorphism, reconstruction, {−1}-hypomorphy, reducible digraphs, Gallai’s decomposition