On the reconstruction of the characteristic polynomial of a graph
type: Item
instance of: scholarly article
title: On the reconstruction of the characteristic polynomial of a graph
zbMATH Open document ID: 0942.05046
DOI: 10.1016/S0012-365X(99)00207-1
published in: Discrete Mathematics
publication date: 2000-08-15T00:00:00Z
review text: \(P_{G}(\lambda) = \text{det}(\lambda I - A) = {\lambda }^n + a_{1}{\lambda }^{n-1}+ \cdots +a_{n-1}\lambda +a_{n} \) is the characteristic polynomoial of the graph \(G\) with adjacency matrix \(A\). Let \({\mathcal P}(G)\) be the collection of characteristic polynomials \(P_{G-x_{i}}(\lambda)\) of the vertex deleted subgraphs \(G-x_{i}\) \((i=1,2,\ldots ,n)\) of \(G\). The author reconsiders the problem of reconstructing \(P_{G}(\lambda)\) uniquely from \({\mathcal P}(G)\), posed by him in 1973. It is well known that this can be solved if \(a_{n}\) can be found from \({\mathcal P}(G)\) and that this is possible if an eigenvalue of \(G\) is known. The problem has been solved earlier for some classes of graphs like regular graphs, a broad class of bipartite graphs, etc. The degree sequence is known to be reconstructible from the deck \({\mathcal P}(G)\). In this paper the author proves that the length of the shortest odd circuit and the number of such circuits and the number of triangles, quadrangles and pentagons, the number of closed walks of length \(k\) \((=0,1,\ldots ,n-1)\) starting and terminating at a vertex \(x_{i}\) and the spectral moments can be computed from \({\mathcal P}(G)\). He also considers a couterexample pair of graphs \(G\) and \(H\) with \({\mathcal P}(G) = {\mathcal P}(H)\) but with different values for \(a_{n}\) and in the case where \(G\) is a tree with a 1-factor, derives several properties of the graph \(H\) (like \(H\) is disconnected, etc.). The problem however, still remains unresolved.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1420212
zbMATH Keywords: graph spectra
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: reconstruction conjecture
zbMATH Keywords: trees
author: Dragoš Cvetković
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00207-1
OpenAlex ID: W2071541852
Wikidata QID: Q127526415
Recommended article: Q4027197
Recommended article: Q3724377
Recommended article: On the construction of graphs determined by their generalized characteristic polynomials
Recommended article: Seeking counterexamples to the reconstruction conjecture for the characteristic polynomial of graphs and a positive results
Recommended article: The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements
Recommended article: Characteristic Polynomial Analysis on Matrix Representations of Graphs
Recommended article: On conjugate characteristic polynomial of a graph
Recommended article: On the \(A_{\alpha}\)-characteristic polynomial of a graph
Recommended article: Q5060665
Recommended article: Q5033137
description: scientific article; zbMATH DE number 1420212