# Connected non-bipartite graphs with a unique perfect matching having highest value of determinant

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?

edit retag close merge delete

Sort by ยป oldest newest most voted

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
if d>maxdet:
res = []
maxdet = d
if d==maxdet:
res.append(G)
print('Max:',maxdet)
print('#graphs:', len(res))

more

Thank you..

( 2024-05-21 18:03:43 +0200 )edit

( 2024-05-22 17:51:01 +0200 )edit

for G in res:
G.show()


You can see them at Sagecell: https://sagecell.sagemath.org/?q=czfqjg

( 2024-05-22 18:28:46 +0200 )edit

ok.But I need those graphs having a unique perfect matching.. see the question

( 2024-05-22 20:38:53 +0200 )edit

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.

( 2024-05-22 22:36:21 +0200 )edit