Jason (jcreed) wrote,

I do so love Lipton's blog. The linked entry mentions the graph reconstruction conjecture which is a beautiful little open problem in graph theory. In one sentence, it is:

A graph (on at least 3 vertices) is uniquely determined by the multiset of all possible vertex deletions of it.

Determined up to isomorphism, that is. A vertex deletion of a graph is the graph you get out of deleting some vertex and all the edges incident to it. You have to say at least 3 vertices because it's just not true for 2! There are only two graphs on 2 vertices, * * and *→*, which both have {*,*} as their multiset of vertex deletions.

There's a related (stronger) conjecture,

A graph (on at least 4 vertices) is uniquely determined by the set of all possible vertex deletions of it

And there you can see the 4 is necessary, because the multiset of vertex deletions of
* *→* is {* *, * *, *-*}, and that of *-*-* is {* *, *-*, *-*}, and these collapse to the same set if we ignore multiplicities, {* *, *-*}.

Here's a question I thought of:
Given n, what is the smallest pair of graphs G and H such that ||D(G) ∩ D(H)|| ≥ n, where D(G) is the set of vertex deletions of G?

I can't even think of graphs such that ||D(G) ∩ D(H)|| ≥ 3! I sort of expect they must exist, though. The thought of there being a constant upper bound on ||D(G) ∩ D(H)|| for all G and H seems absurd. I bet this could be refuted by playing with the output of Nauty, which contains tools for generating all nonisomorphic graphs over n vertices, and testing graph isomorphism.


Ah, thought of a pair over four vertices just by pencil-and-paper brute force.

   |  |

both possess vertex deletions
o--o   o--o
|      |
o--o   o


and then each has one more that distinguishes them.


Another example that is smaller with respect to jointly how many distinct vertex deletions exist of of G (3) and H (4):

G           H
  o---o       o---o
 / \ / \     / \ / \
o---o---o   o---o   o

Maybe the right question to ask is how small you can get the distinct sets of vertex deletions of the pair
such that their intersection is at least n big. In this case (||D(G)||,||D(H)||) = (n,n+1) for ||D(G)∩D(H)||=n is as close as you can get without violating the second conjecture above (which violation would require (n,n)), and this does in fact obtain for n=1,2,3.
Tags: graphs, math
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded