The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements

  • Elias M. Hagos

Abstract

The question of whether the characteristic polynomial of a simple graph is uniquely determined by the characteristic polynomials of its vertex-deleted subgraphs is one of the many unresolved problems in graph reconstruction. In this paper we prove that the characteristic polynomial of a graph is reconstructible from the characteristic polynomials of the vertex-deleted subgraphs of the graph and its complement.

Published
2000-02-13
Article Number
R12