1
$\begingroup$

Given $q \in \mathbb{N}$, let $B_q$ be a sequence of all (non isomorphic) connected graphs with at most $q$ vertices. Now for a given connected graph $G$, lets define signature of $G$ ($sig_q(G)$) as an integer-valued vector of length $|B_q|$ such that $sig_q(G)[i]=$ number of occurrences of graph $B_q[i]$ in $G$.

The question is: how large $q$ do we have to take so that any graph on $n$ vertices is uniquely determined by $sig_q(G)$?

I thought that it would be sufficient to take $q$ close to the diameter of $G$, but the following counter-example shows two graphs with diameter 4 that have the same $sig_4$ but are not isomorphic.

Two non-isomorphic graphs with the same signature

Improve this question
$\endgroup$
1
  • $\begingroup$ This sounds like a problem related to the reconstruction conjecture. You might see if the variation involving graphs of degree smaller than n-1 has been posed. Gerhard "Suspects An Easily Proved Equivalence" Paseman, 2019.09.02. $\endgroup$
    – Gerhard Paseman
    Commented Sep 2, 2019 at 21:27

1 Answer 1

Reset to default
3
$\begingroup$

If you can answer this question, and prove it, you'll be famous. It is the reconstruction problem that has been open since 1957.

Basically, except for the trivial case $n=2$, nobody can prove that even $q=n-1$ is enough. Lots of people have tried, though.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .