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