Reconstructibility of graphs with a large branch: Permutation group theory and graph reconstruction (Q1270630)

In [\textit{V. Krishnamoorthy} and \textit{K. R. Parthasarathy}, On the reconstruction conjecture for separable graphs, J. Aust. Math. Soc., Ser. A 30, 307-320 (1981; Zbl 0472.05047)] it was proved that if \(G\) is a connected graph whose pruned center \(P\) (center of the graph obtained from \(G\) by successively removing pendant vertices, till the resulting graph has no pendant vertices) is a block and \(G\) satisfies the conditions (1) \(G\) has a pendant vertex \(v\) such that \(G-v\) has pendant vertices in at least two of its branches, and (2) \(G\) has a branch \(B\) with a non-cut-vertex \(u\) of \(B\) such that \(B-u\) is not isomorphic to any branch of \(G\), then \(G\) is branch reconstructible (that is, reconstructible from the deck of cards \(G-v\) where \(v\) is a vertex of \(G\) not in \(P\)). Here, the authors take up the negation of condition (2), keeping other things unaltered, and prove that, in this case, either \(G\) is branch reconstructible, or the vertex set \(V(P)= X\) of the pruned center has an \(A\)-reconstructible partition \(X= X_0\cup X_1\cup\cdots\cup X_m\) \((m\geq 1)\), where \(A\) is the automorphism group of the induced subgraph on \(P\), and \(X_j= \{x\in X\mid x\) the root of a branch \(B\) for which \(| V(B)|= j+2\}\) for \(j\geq 1\) and \(X_0= X\setminus (X_1\cup X_2\cup\cdots\cup X_m)\). For a permutation group \(A\) acting on a set \(X\) an \(A\)-reconstructible partition of \(X\) is defined as \(X= X_0\cup X_1\cup\cdots\cup X_m\), in which for every \(i\geq 1\) and \(x\in X_i\) there is an element \(a= a_x\in A\) such that (1) \(x^a\in X_{i- 1}\), (2) there is \(y\in X_{i-1}\) for which \(y^a\in X_i\), (3) \((X_i\setminus\{x\})^a\subseteq X_i\), (4) \((X_{i-1} \setminus\{y\})^a\subseteq X_{i-1}\), and (5) \(X^a_j= X_j\) for all \(j\neq i- 1, i\). This leads to the proof that if \(G\) is a connected graph, with pruned center \(P\) a block, that satisfies condition (1) and the negation of condition (2) and the further condition that \(G\) has a branch \(B\) with \(| V(B)|>(| V(P)|/2)+ 2\), then \(G\) is branch reconstructible. This considerably enhances the classes of graphs for which the reconstruction conjecture is true.