Skip to main content
added 5 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

The answer to Question I is yesyes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I This characterizes the bipartite graphs with exactly one perfect matching. The

Regarding your other questions, the graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if the number of perfect matchings of a general bipartite graph hasis exactly zero or one perfect matchings is to computeas follows. Compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if a general bipartite graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees. This characterizes the bipartite graphs with exactly one perfect matching.

Regarding your other questions, the graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if the number of perfect matchings of a general bipartite graph is exactly zero or one is as follows. Compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

added 18 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if a general bipartite graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if a graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if a general bipartite graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

added 82 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question II is no. For example, the biadjacency matrix ofI characterizes the complete bipartite graph $K_{n,n}$ togethergraphs with two isolated vertices cannot be permuted to a lower triangular matrix, but this graph hasexactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

For Question III,One way to decide if a graph has exactly zero or one optionperfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question II is no. For example, the biadjacency matrix of the complete bipartite graph $K_{n,n}$ together with two isolated vertices cannot be permuted to a lower triangular matrix, but this graph has zero perfect matchings.

For Question III, one option is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to Question I characterizes the bipartite graphs with exactly one perfect matching. The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.

One way to decide if a graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time). If the maximum matching is not a perfect matching, then the graph has zero perfect matchings. If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.

added 207 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Loading