patternMinor
Complete graph invariant
Viewed 0 times
completeinvariantgraph
Problem
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)?
Solution
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
-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()Code Snippets
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()Context
StackExchange Computer Science Q#14147, answer score: 5
Revisions (0)
No revisions yet.