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()