5
$\begingroup$

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

$\endgroup$

2 Answers 2

5
$\begingroup$

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)
        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()
$\endgroup$
4
  • $\begingroup$ ok, thank you. a curiosity: does the "det" function return 1 for an empty matrix? $\endgroup$ Commented Sep 5, 2013 at 14:30
  • $\begingroup$ Yes: sage: matrix([]).det() sage: 1 $\endgroup$
    – Jernej
    Commented Sep 5, 2013 at 16:08
  • $\begingroup$ Interesting that the smallest isospectral graph example worked out. Does it work in general for isospectral graphs? $\endgroup$
    – A.Schulz
    Commented Sep 5, 2013 at 16:42
  • $\begingroup$ @A.Schulz I suspect it does not, though being cospectral is a necessary condition. $\endgroup$
    – Jernej
    Commented Sep 6, 2013 at 9:25
0
$\begingroup$

Let $A$ be the adjacency matrix of the graph and let $A_{ij}$ be its minors. It is known then $(A^{-1})_{ij} = (-1)^{i+j} \det A_{ji}/\det A$. So the original graph can be recovered from your data. (The determinants of the cofactors determine $A^{-1}$, and so $A$, up to a constant factor, and (unless the graph is empty) there is a unique choice that leads to a $0,1$ inverse.)

Suppose first that the collection of determinants of principal minors is ordered. Take any graph with a non-trivial automorphism (e.g. a square), and consider two different isomorphic representations. These will have different invariants but be isomorphic.

Suppose next that the collection of determinants of principal minors is not ordered. Any two isospectral graphs with the same number of edges will have the same invariants up to sign (i.e. the same collection of absolute values of determinants of cofactors) since they have the same overall determinant and the same number of $0$s and $1$s. So probably if you try several pairs you'll find one where the unordered invariants are exactly the same.

$\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.