Reconstruction number of graphs with unique pendant vertex (Q2235292)

The reconstruction number of a graph is the minimum number of one-vertex-deleted subgraphs that will determine the graph up to isomorphism. This definition is of course only meaningful when the graph is reconstructible. A \(P\)-graph is a graph that has \(p\) vertices and two blocks (maximal connected subgraphs without cutvertices), one pendant vertex \(x\), attached to a base vertex \(r\), and a vertex \(u\not= r\) that is adjacent to all vertices except \(x\). For the following types of \(P\)-graphs, it is proved that the reconstruction number is \(3\): \(P\)-graphs with at most one 2-vertex, \(P\)-graphs with at least two 2-vertices and a vertex \(v\not= u\) with degree greater than or equal to \(p-3\), \(P\)-graphs with at least two 2-vertices such that all vertices \(v\not= u\) have degree less than or equal to \(p-4\) and at most one neighbor of a 2-vertex is adjacent to exactly one 2-vertex. The three cards used for reconstruction are \(G-x\) and \(G-r\) and either \(G-u\) or \(G-s\), where \(s\) is a 2-vertex. The paper concludes with a reduction theorem that states that the reconstruction number for all graphs is equal to \(3\) iff it is equal to 3 for all 2-connected graphs; for all separable graphs; for all \(P\)-graphs with at least two 2-vertices such that all vertices not equal to \(u\) have degree \(\leq p-4\) and at least two vertices \(t\not\in \{ u,r\} \) are adjacent to exactly one \(2\)-vertex each; for all \(Q\)-graphs (graphs with \(p\) vertices and exactly one \((p-2)\)-vertex \(w\), exactly one pendant vertex \(y\) whose base \(q\) is not equal to \(w\) such that \(G\) is the union of the endblock that contains \(y\), the endblocks that contain \(w\) and the nonendblock that contains \(w\) and \(q\)); and for all \(R\)-graphs (graphs with \(p\) vertices and exactly two pendant vertices, which are adjacent to distinct \((p-2)\)-vertices).