Skip to main content

Relation between two conjectures on reconstruction of graphs

In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.

Also, we have a result by professor Béla Bollobás that says: Almost every graph has reconstruction number three ($RC=$ Almost every graph is reconstructible).

We have a theorem in spectral graph theory that says: We can construct the characteristic polynomial of a graph by its deck. I have two questions:

  1. Can we say something like that: Almost every graph has a characteristic polynomial reconstruction number $k < n$? For example $k=3$. By characteristic polynomial reconstruction number $3$, I mean if we have a $3$ suitable graphs in the deck of the original graph, we can obtain its characteristic polynomial.

  2. What is the problem if we say that $RC\rightarrow DS$ or $DS\rightarrow RC$? Is it because we work with the words "Almost every ..."?

Thank you in advance for your notes and guidance.

Shahrooz
  • 4.8k
  • 1
  • 24
  • 36