Complete graph invariant

Question

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph is a complete invariant for graph isomorphism (i.e. that multiset uniquely identifies a graph up to isomorphism)?

Thanks!

Answer 1

The answer is no. A counterexample is given by the following two graphs both having $(-1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1) $ as the multiset that you describe.

If you want to play further, you can use the following Sage program that found them

def tupleDet(G):
    A = G.am()
    L =  []  
    for sub in subsets(range(G.order())):    
        D = A.matrix_from_rows_and_columns(sub,sub)
        L.append(D.det())

    return tuple(sorted(L))    


def search(n):
    d= {}
    for G in graphs.nauty_geng(str(n)):
        des = tupleDet(G)
        if des in d:
            print G.graph6_string(), d[des]
            return
        else:
            d[des] = G.graph6_string()

Answer 2

Since the determinant of the whole matrix is reconstructible from the order $n-1$ principal minors (Tutte) and the multisets of smaller determinants are obviously determined by those minors, an affirmative answer would affirmatively answer the Ulam reconstruction problem. From this, we can infer that nobody has proved it. On the other hand, it could be disproved by a counterexample; I'm not aware of one.