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

Anonymous

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


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 close merge delete

Sort by ยป oldest newest most voted

This is similar to Ask Sage question 63102.

• 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):
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.

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?

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

( 2023-01-11 22:13:19 +0200 )edit
1

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?

( 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:
g.show()

( 2023-01-14 06:19:16 +0200 )edit