Ask Your Question
0

How to find the graphs having exactly one perfect matching from the following collection?

asked 2022-07-04 08:11:57 +0200

anonymous user

Anonymous

updated 2022-07-06 13:43:44 +0200

Max Alekseyev gravatar image

.

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

Here I am trying to obtain those graphs which have a unique perfect matching, that is, those graphs which have exactly one perfect matching.

edit retag flag offensive close merge delete

Comments

Check again the definition of perfect matching https://en.wikipedia.org/wiki/Perfect.... For graphs of order 7, the answer is obvious from the definition: none.

David Coudert gravatar imageDavid Coudert ( 2022-07-04 09:02:00 +0200 )edit

You are correct. I have edited my code now..Can we find now?

rewi gravatar imagerewi ( 2022-07-04 09:04:46 +0200 )edit

You can use method perfect_matchings and discard graphs with more than 1 perfect matching.

David Coudert gravatar imageDavid Coudert ( 2022-07-04 17:41:03 +0200 )edit

It'd be more efficient to request specific number of edges from nauty: '8 10:10 -c' rather than checking if g.size()==10:

Max Alekseyev gravatar imageMax Alekseyev ( 2022-07-06 13:45:24 +0200 )edit
slelievre gravatar imageslelievre ( 2023-01-10 20:59:04 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-07-05 09:01:28 +0200

By a theorem of Berge, if a graph G with a perfect matching M contains an alternating cycle, then the perfect matching is not unique. Several algorithms to check uniqueness of a perfect matching have been proposed. See for instance the algorithm by Gabow, Kaplan and Tarjan https://doi.org/10.1006/jagm.2001.1167

A more brute force approach, based on methods already available in Sagemath, is the following:

def has_unique_perfect_matching(g):
    j = 0
    for _ in g.perfect_matchings():
        j += 1
        if j == 2:
            # more than one perfect matching
            break
    return j == 1

def graphs_with_unique_perfect_matching(n):
    i = 0
    for g in graphs.nauty_geng('{} -c'.format(n)):
        if has_unique_perfect_matching(g):
            i += 1
            print(i, g.graph6_string())

You get:

sage: graphs_with_unique_perfect_matching(5)
sage: graphs_with_unique_perfect_matching(6)
1 ECR_
2 ECRo
3 ECRw
4 ECr_
5 ECpo
6 ECqg
7 ECro
8 ECrg
9 ECrw
10 ECZ?
11 ECZO
12 ECZG
13 ECZW
14 ECzW
15 ECvo
16 ECuw
17 ECvw
18 EEiW
19 EEhW
20 EQjO
sage: graphs_with_unique_perfect_matching(7)
sage: graphs_with_unique_perfect_matching(8)
1 G?`@F_
2 G?`@Fo
3 G?`@Fw
4 G?`@F{
5 G?`DE_
...
654 GCQRVO
655 GCQRUS
656 GCQRVS
edit flag offensive delete link more

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

Stats

Asked: 2022-07-04 08:11:57 +0200

Seen: 252 times

Last updated: Jul 06 '22