The polynomial reconstruction problem for graphs having cut-vertices of degree two

In the polynomial reconstruction problem (PRP), the characteristic polynomial ϕ ( G , x ) of a graph G is sought from the polynomial deck PD ( G ) containing the characteristic polynomials of the n vertex-deleted subgraphs of G . The diagonal entries of the adjugate matrix adj ( G , x ) of G are the elements of PD ( G ) . The PRP is not completely solved for graphs having vertices of degree one. In this paper, we use adj ( G , x ) to successfully obtain ϕ ( G , x ) from PD ( G ) for certain graphs having a vertex of degree one whose characteristic polynomial is not discoverable using results from current literature. Our methods require such graphs to have a vertex of degree one adjacent to a vertex of degree two, and this latter vertex would then be a cut-vertex of G . We thus extend this idea to partially solve the PRP for more general graphs that have a cut-vertex of degree two which is not necessarily adjacent to vertices of degree one, presenting an algorithm that provides ϕ ( G , x ) from PD ( G ) when G has such a cut-vertex.