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



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.

enter image description here

enter image description here

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)

    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]
            d[des] = G.graph6_string()
  • $\begingroup$ These are the smallest pair of graphs with the same eigenvalues, though that doesn't by itself explain the result (or does it?). $\endgroup$ – Brendan McKay Sep 6 '13 at 1:13
  • $\begingroup$ @BrendanMcKay Not sure it does. There are cospectral graphs with different multisets (as defined here) $\endgroup$ – Jernej Sep 6 '13 at 9:47

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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