Ask Your Question

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

asked 2024-05-21 14:07:54 +0200

rewi gravatar image

updated 2024-05-21 14:08:19 +0200

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

1 Answer

Sort by ยป oldest newest most voted

answered 2024-05-21 17:29:05 +0200

Max Alekseyev gravatar image

updated 2024-05-23 21:38:58 +0200

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:
    d = abs(G.adjacency_matrix().det())
    if d>maxdet:
        res = []
        maxdet = d
    if d==maxdet:
print('#graphs:', len(res))
edit flag offensive delete link more


Thank you..

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

Can you please help me in displaying those graphs, maximizing the determinant?

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

Add something along these lines:

for G in res:

You can see them at Sagecell:

Max Alekseyev gravatar imageMax Alekseyev ( 2024-05-22 18:28:46 +0200 )edit

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

rewi gravatar imagerewi ( 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.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-05-22 22:36:21 +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


Asked: 2024-05-21 14:07:54 +0200

Seen: 269 times

Last updated: May 23