Description of the digraphs $\{-1\}$-hypomorphic to a reducible digraph - Université de La Réunion Access content directly
Journal Articles Journal of Multiple-Valued Logic and Soft Computing Year : 2024

Description of the digraphs $\{-1\}$-hypomorphic to a reducible digraph

Abstract

Let $G$ be a digraph with vertex set $V$. A module of $G$ is a set $M$ of vertices indistinguishable by the vertices outside $M$. A module of $G$ distinct from $V$ is a proper module of $G$. The digraph $G$ is reducible if its vertex set $V$ is the union of two proper modules. A digraph $G^{\prime}$, defined on $V$, is $\{-1\}$-hypomorphic to $G$ whenever the subdigraphs of $G$ and $G^{'}$ induced by $V\setminus\{x\}$ are isomorphic, for every vertex $x$. The digraph $G$ is $\{-1\}$-reconstructible if it is isomorphic to each digraph it is $\{-1\}$-hypomorphic to it. In this paper, given a reducible digraph $G$ having more than $4$ vertices, we describe the digraphs that are $\{-1\}$-hypomorphic to $G$. 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$.
No file

Dates and versions

hal-04520902 , version 1 (25-03-2024)

Licence

Copyright

Identifiers

  • HAL Id : hal-04520902 , version 1

Cite

Mouna Achour, Youssef Boudabbous, Abderrahim Boussaïri. Description of the digraphs $\{-1\}$-hypomorphic to a reducible digraph. Journal of Multiple-Valued Logic and Soft Computing, In press, MVLSC special issue Ivo G Rosenberg. ⟨hal-04520902⟩
19 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More