Suppose we consider the class of connected non-bipartite graphs with a unique perfect matching with 10 vertices and 12 edges. Now from this collection, how one can obtain the graph(s) whose adjacency matrix has highest absolute value of its determinant?
The following code tells that the max absolute value of determinant is 9 and there are 4 such graphs achieving it:
maxdet = 0
res = []
for G in graphs.nauty_geng('-c 10 12'):
if G.is_bipartite() or abs(G.matching_polynomial()[0])!=1:
continue
d = abs(G.adjacency_matrix().det())
if d>maxdet:
res = []
maxdet = d
if d==maxdet:
res.append(G)
print('Max:',maxdet)
print('#graphs:', len(res))
Add something along these lines:
for G in res:
G.show()
You can see them at Sagecell: https://sagecell.sagemath.org/?q=czfqjg
They do have a unique perfect matching. In my code this is controlled by the requirement for G.matching_polynomial()[0] to be equal -1.
Asked: 2024-05-21 14:07:54 +0200
Seen: 194 times
Last updated: May 23
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
