The \((\leq k)\)-half-reconstructability of graphs for \(7\leq k\leq 12\). (Q2828847)

The dual of a directed graph \(G=(V,A)\) is the directed graph \(G^*=(V,A^*)\) with \(A^*=\{ (y,x):(x,y)\in A\}\). Two directed graphs \(G=(V,A)\) and \(G'=(V',A')\) are called dually isomorphic iff \(G^*\) and \(G'\) are isomorphic. They are called hemimorphic iff they are isomorphic or dually isomorphic. Two directed graphs \(G=(V,A)\) and \(G'=(V,A')\) on the same vertex set \(V\) are called \((\leq k)\)-hypomorphic (hemimorphic) iff, for all \(X\subset V\) with \(|X|\leq k\), we have that the induced directed subgraphs \(G[X]\) and \(G'[X]\) are isomorphic (hemimorphic). A directed graph \(G=(V,A)\) is called \(\leq k\)-(half-)reconstructible iff, for all \((\leq k)\)-hypomorphic (hemimorphic) directed graphs \(G'\), we have that \(G\) is isomorphic (hemimorphic) to \(G'\).NEWLINENEWLINE Finite directed graphs are known to be \((\leq 12)\)-half-reconstructible and, for \(7\leq k\leq 11\), the \((\leq k)\)-half-reconstructible finite directed graphs have been characterized. The present paper characterizes, for \(7\leq k\leq 12\), all \((\leq k)\)-half-reconstructible directed graphs. As is the case with many results on reconstruction, statements and proofs can become quite technical. Because the paper extends characterizations from the finite to the infinite scenario, it requires extensive quotes from the literature, which are summarized in pages 195 to 201.NEWLINENEWLINE A chain is a directed graph whose arcs comprise a transitive relation such that any two vertices are joined by an arc. A directed graph on vertices \(\{ v_j : j\in \mathbb{N}\}\) such that either, for any two non-consecutive integers \(i\) and \(k\), we have that neither \((v_i,v_k)\) nor \((v_k,v_i)\) is an arc, or, such that, for any two non-consecutive integers \(i\) and \(k\), we have that both \((v_i,v_k)\) and \((v_k,v_i)\) are arcs is called a potentially augmented semi-infinite path (consécutivité infinies à une seule extrémité) iff either, for all \(j\in\mathbb{N}\), we have that \((v_j,v_{j+1})\) is an arc, or, for all \(j\in\mathbb{N}\), we have that \((v_{j+1},v_j)\) is an arc. An autonomous subset of a directed graph \(G=(V,A)\) is a set of vertices \(M\) such that, for all \(x\not\in M\) and \(y,z\in M\), we have that \((x,y)\in M\) iff \((x,z)\in M\) and \((y,x)\in M\) iff \((z,x)\in M\). Let \(G=(V,A)\) be a directed graph and let \(M\) be an autonomous subset of \(G\). Then \(G_M\) is the directed graph obtained from \(G\) by turning \(M\) into a vertex, which has in-arcs from all vertices \(v\) that have an arc into \(M\) and which has out-arcs to all vertices \(v\) for which \(M\) has a vertex with an out-arc to \(v\).NEWLINENEWLINE Central to the paper is the following result (Théorème 18): An infinite directed graph \(G=(V,A)\) is not \((\leq 12)\)-half-reconstructible iff one of the following holds.NEWLINE{\parindent=0.7cm \begin{itemize}\item[1.] \(G\) has an autonomous chain.NEWLINE\item[2.] \(G\) has 2 autonomous subsets such that the induced directed subgraph on each is a potentially augmented semi-infinite path.NEWLINE\item[3.] \(G\) has exactly one autonomous subset \(M\) whose induced directed subgraph is a potentially augmented semi-infinite path and, for this autonomous subset \(M\), there is no isomorphism \(g\) from \(G_M\) to \(G_M^*\) such that \(g[M]=M\).NEWLINENEWLINE\end{itemize}}NEWLINEThe 4 page proof relies, for one direction, on constructing examples that each of the conditions precludes \((\leq 12)\)-half-reconstructibility and, for the other direction, on proving that \((\leq 12)\)-hemimorphic directed graphs \(G\) and \(G'\) are such that \(G\) and \(G'\) are \((\leq 6)\)-hypomorphic or such that \(G^*\) and \(G'\) are \((\leq 6)\)-hypomorphic, which, under the conditions in the theorem, implies that \(G\) and \(G'\) are hemimorphic.NEWLINENEWLINE The remaining 20 pages of the paper comprise a sequence of theorems that, starting with \(d=11\) and ending with \(d=7\), characterize when a \((\leq d+1)\)-half-reconstructible directed graph is not \((\leq d)\)-half-reconstructible.