[FORTHCOMING] Sur la somme lexicographique d’un digraphe premier et rigide et la {-1}-hypomorphie

This work involves the reconstruction in the sense of Ulam. Let $$$G$$$ and $$$G'$$$ be two digraphs with the same vertex set $$$V$$$. The digraphs $$$G$$$ and $$$G'$$$ are $$$\{-1\}$$$-hypomorphic if the induced subdigraphs $$$G-x$$$ and $$$G'-x$$$ are isomorphic for every vertex $$$x$$$. The digraph $$$G$$$ is $$$\{-1\}$$$-reconstructible if it is isomorphic to every digraph to which it is $$$\{-1\}$$$-hypomorphic. In a digraph $$$G$$$, a module is a vertex subset $$$M$$$ such that every vertex outside $$$M$$$ does not distinguish the vertices in $$$M$$$. For instance, $$$\emptyset$$$, $$$V(G)$$$, and the single-vertex sets are modules of $$$G$$$, called trivial modules. A module distinct from $$$V(G)$$$ is a proper module of $$$G$$$. A digraph is indecomposable if all its modules are trivial ; otherwise, it is decomposable. Every indecomposable digraph with at least $$$3$$$ vertices is prime. A digraph is rigid if the unique automorphism of $$$G$$$ is the identity on $$$V(G)$$$.
In this paper, given an $$$n$$$-vertex digraph $$$G$$$, with $$$n\geq 7$$$, that can be expressed as a lexicographical sum over a prime and rigid digraph with at most $$$n-2$$$ vertices, we describe the digraphs that are $$$\{-1\}$$$-hypomorphic to $$$G$$$, and in particular we prove that $$$G$$$ is $$$\{-1\}$$$-reconstructible.

This work involves the reconstruction in the sense of Ulam. Let $$$G$$$ and $$$G'$$$ be two digraphs with the same vertex set $$$V$$$. The digraphs $$$G$$$ and $$$G'$$$ are $$$\{-1\}$$$-hypomorphic if the induced subdigraphs $$$G-x$$$ and $$$G'-x$$$ are isomorphic for every vertex $$$x$$$. The digraph $$$G$$$ is $$$\{-1\}$$$-reconstructible if it is isomorphic to every digraph to which it is $$$\{-1\}$$$-hypomorphic. In a digraph $$$G$$$, a module is a vertex subset $$$M$$$ such that every vertex outside $$$M$$$ does not distinguish the vertices in $$$M$$$. For instance, $$$\emptyset$$$, $$$V(G)$$$, and the single-vertex sets are modules of $$$G$$$, called trivial modules. A module distinct from $$$V(G)$$$ is a proper module of $$$G$$$. A digraph is indecomposable if all its modules are trivial; otherwise, it is decomposable. Every indecomposable digraph with at least $$$3$$$ vertices is prime. A digraph is rigid if the unique automorphism of $$$G$$$ is the identity on $$$V(G)$$$.
In this paper, given an $$$n$$$-vertex digraph $$$G$$$, with $$$n\geq 7$$$, that can be expressed as a lexicographical sum over a prime and rigid digraph with at most $$$n-2$$$ vertices, we describe the digraphs that are $$$\{-1\}$$$-hypomorphic to $$$G$$$, and in particular we prove that $$$G$$$ is $$$\{-1\}$$$-reconstructible.

Lexicographical sum {−1}-reconstruction {−1}-hypomorphy irreducible digraphs rigid digraphs Gallai’s (modular) decomposition

Lexicographical sum {−1}-reconstruction {−1}-hypomorphy irreducible digraphs rigid digraphs Gallai’s (modular) decomposition