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

Abstract

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.