La \((\leq k)\)-Demi-Reconstructibilité Des Graphes Pour \(7\leq k\leq12\)

Abstract

Let \(G = (V, A)\) be a graph. For every subset \(X\) of \(V\), the sub-graph \(G(X) = (X, A \cap (X \times X))\) of \(G\) induced by \(X\) is associated. The dual of \(G\) is the graph \(G^* = (V, A^*)\)such that \(A^* = \{(x,y): (y,x) \in A\}\). A graph \(G’\) is hemimorphic to \(G\) if it is isomorphic to \(G\) or \(G^*\). Let \(k \geq 1\) be an integer. A graph \(G’\) defined on the same vertex set \(V\) of \(G\) is \((\leq k)\)-hypomorphic (resp. \((\leq k)\)-hemimorphic) to \(G\) if for all subsets \(X\) of \(V\) with at most \(k\) elements, the sub-graphs \(G(X)\) and \(G'(X)\) are isomorphic (resp. hemimorphic). \(G\) is called \((\leq k)\)-reconstructible (resp. \((\leq k)\)-half-reconstructible) provided that every graph \(G’\) which is \((\leq k)\)-hypomorphic (resp. \((\leq k)\)-hemimorphic) to \(G\) is hypomorphic (resp. hemimorphic) to \(G\). In 1972, G. Lopez {14,15] established that finite graphs are \((\leq 6)\)-reconstructible. For \(k \in \{3,4,5\}\), the \((<k)\)-reconstructibility problem for finite graphs was studied by Y. Boudabbous and G. Lopez [1,5]. In 2006, Y. Boudabbous and C. Delhommé [4] characterized, for each \(k \geq 4\), all \((\leq k)\)-reconstructible graphs. In 1993, J. G. Hagendorf and G. Lopez showed in [12] that finite graphs are \((\leq 12)\)-half-reconstructible. After that, in 2003, J. Dammak [8] characterized the \((\leq k)\)-half-reconstructible finite graphs for every \(7 \leq k \leq 11\). In this paper, we characterize for each integer \(7 \leq k \leq 12\), all \((\leq k)\)-half-reconstructible graphs.