Ask Your Question

How to find the graphs having exactly one perfect matching from the following collection and whose determinant is maximum?

asked 2023-01-10 20:20:05 +0200

anonymous user


for g in graphs.nauty_geng('8 -c'):
                    if g.size()==10:

Here I am trying to obtain those graph(s) which have exactly one perfect matching and among all those graphs I need to obtain only that graph(s) whose adjacency matrix have highest determinant.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2023-01-10 20:57:01 +0200

slelievre gravatar image

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:
            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()


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

and we find 2 graphs with determinant -7.

edit flag offensive delete link more


Thank you. But I am unable to compile your code. Can you please provide all the codes in a single code so that I can complile directly?

rewi gravatar imagerewi ( 2023-01-11 09:57:53 +0200 )edit

Here is a link:

slelievre gravatar imageslelievre ( 2023-01-11 22:13:19 +0200 )edit

OK, Thanks. Now suppose I want to find the graphs having exactly one perfect matching from the following collection : Consider the class of simple connected graphs with 10 vertices and having 13 edges. Now from this collection, I want to find the graphs having exactly one perfect matching and having maximum determinant. Is it possible to find?

rewi gravatar imagerewi ( 2023-01-13 20:05:45 +0200 )edit

Call the function with the appropriate arguments:

my_graphs = graphs_with_max_det_and_unique_perfect_matching(order=10, size=13)

Check how many graphs you got and what determinant they have:

len(my_graphs), set(g.adjacency_matrix().det() for g in my_graphs)

Display the graphs:

for g in my_graphs:
slelievre gravatar imageslelievre ( 2023-01-14 06:19:16 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2023-01-10 20:20:05 +0200

Seen: 488 times

Last updated: Jan 10 '23