3
$\begingroup$

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of (isomorphism classes) of simple graphs that can be obtained by adding a single edge to $G$. Is $G$ uniquely determined by $E^-(G)$ and $E^+(G)$? Thank you in advance!

Are there any other examples besides the two graphs on 4 vertices?

$\endgroup$
1
  • 1
    $\begingroup$ Do you mean to have the data as sets or as multisets? Are the edge deleted subgraphs given with multiplicity? $\endgroup$ Nov 23, 2013 at 7:22

2 Answers 2

5
$\begingroup$

Let $V=\{a,b,c,d\}$, $E_1=\{(a,b),(a,c),(a,d)\}$, $E_2=\{a,b),(a,c),(b,c)\}$, $G_1=(V,E_1)$, and $G_2=(V,E_2)$. Then $E^-(G_1)=E^-(G_2)$ and $E^+(G_1)=E^+(G_2)$ although $G_1$ and $G_2$ are not isomorphic.

$\endgroup$
1
  • $\begingroup$ It couls very wel be the only example... $\endgroup$ Feb 22, 2014 at 0:34
4
$\begingroup$

Except for finitely many cases, $G$ can be reconstructed from the largest of $E^-(G)$ and $E^+(G)$. Note that you have the edge-decks of both $G$ and its complement.

Lovász proved that $G$ is edge-reconstructible if it has more edges than its complement. That covers all cases except when $G$ has exactly $n(n-1)/4$ edges.

Müller proved that graphs with more than $n(\log_2(n)-1)$ edges are edge-reconstructible. That finishes it for all $n\ge 12$. The cases $n=10,11$ don't happen, as $n(n-1)/4$ is not an integer. So you are left with $n\le 9$ which has been done exhaustively by computer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.