2023/10/11 by Zhang, Jingyuan, Jin, Xian'an, Yan, Weigen +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.07104
As a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetković and Schwenk posed independently the following problem: Can the characteristic polynomial of a simple graph G with vertex set V be reconstructed from the characteristic polynomials of all subgraphs in \G-v|v∈ V\ for |V|≥ 3? This problem is still open. A natural problem is: Can the characteristic polynomial of a simple graph G with edge set E be reconstructed from the characteristic polynomials of all subgraphs in \G-e|e∈ E\? In this paper, we prove that if |V|≠ |E|, then the characteristic polynomial of G can be reconstructed from the characteristic polynomials of all subgraphs in \G-uv, G-u-v|uv∈ E\, and the similar result holds for the permanental polynomial of G. We also prove that the Laplacian (resp. signless Laplacian) characteristic polynomial of G can be reconstructed from the Laplacian (resp. signless Laplacian) characteristic polynomials of all subgraphs in \G-e|e∈ E\ (resp. if |V|≠ |E|).