Revision history [back]

This is similar to Ask Sage question 63102.

The comments and answers there:

• point out that Nauty allows to specify order and size
• provide a function has_unique_perfect_matching

One could use that to build a new function:

def graphs_with_max_det_and_unique_perfect_matching(order=8, size=10):
    max_det = -oo
    graph_list = []
    for g in graphs.nauty_geng(f'{order} {size}:{size} -c'):
        if has_unique_perfect_matching(g):
            d = g.adjacency_matrix().det()
            if d == max_det:
                graph_list.append(g)
            if d > max_det:
                max_det = d
                graph_list = [g]
    return graph_list

Using this function for graphs on 8 vertices with 10 edges:

sage: my_graphs = graphs_with_max_det_and_unique_perfect_matching(order=8, size=10)
sage: len(my_graphs), set(g.adjacency_matrix().det() for g in my_graphs)

we find there are 127 graphs with unique perfect matching and determinant one.

If we instead care about the maximum absolute value of the determinant, we replace

            d = g.adjacency_matrix().det()

by

            d = g.adjacency_matrix().det().abs()

and we find 2 graphs with determinant -7.