On the \(\{4, -k\}\)-hypomorphy for digraphs

Abstract

Let \(k\) be a non-negative integer. Two digraphs \(G = (V, A)\) and \(G’ = (V, A’)\) are \(\{k\}\)-hypomorphic if for all \(k\)-element subsets \(K\) of \(V\), the subdigraphs \(G[K]\) and \(G'[K]\) induced on \(K\) are isomorphic. The equivalence relation \(\mathcal{D}_{G,G’}\) on \(V\) is defined by: \(x \mathcal{D}_{G,G’} y\) if \(x = y\) or there exists a sequence \(x_0 = x, \ldots, x_n = y\) of elements of \(V\) satisfying \((x_i, x_{i+1}) \in A\) if and only if \((x_i, x_{i+1}) \in A’\), for all \(i\), \(0 < i k + 6\). If \(G\) and \(G’\) are two digraphs, \(\{4\}\)-hypomorphic and \(\{v – k\}\)-hypomorphic on the same vertex set \(V\) of \(uv\) vertices, and \(C\) is an equivalence class of the equivalence relation \(\mathcal{D}_{G,G’}\), then \(G'[C \setminus A]\) and \(G[C \setminus A]\) are isomorphic for all subsets \(A\) of \(V\) of at most \(k\) vertices. In particular, \(G'[C]\) and \(G[C]\) are \(\{v – k – h\}\)-hypomorphic for all \(h \in \{1, 2, \ldots, k\}\), and \(G'[C]\) and \(G[C]\) (resp. \(G’\) and \(G\)) are isomorphic. In particular, for \(k = 1\) and \(k = 4\) we obtain the result of G. Lopez and C. Rauzy [7]. As an application of the main result, we have: If \(G\) and \(G’\) are \(\{v – 4\}\)-hypomorphic on the same vertex set \(V\) of \(v > 10\) vertices, then \(G[X]\) and \(G'[X]\) are isomorphic for all subsets \(X\) of \(V\); the particular case of tournaments was obtained by Y. Boudabbous [2].