0
$\begingroup$

It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the permanent of the adjacency matrix of an odd order graph, then what does its integer part bound? Does it bound the number of distinct maximum matchings?

In the paper referred above, it is proved that the permanent of the adjacency matrix measures the number of $2$-spanning subgraphs that consist of even cycles. Suppose, even for an even order graph, if it does not have a perfect matching, then does the square root of the number of spanning $2$-regular subgrpahs bound the number of maximum matchings? Any lights on these matters? Thanks beforehand.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ For number of perfect matchings look up hafnian $\endgroup$
    – Robert Israel
    Commented Aug 26, 2022 at 20:20
  • $\begingroup$ @RobertIsrael great! Does hafnian of odd order graph similarly give number of maximum matchings? $\endgroup$
    – vidyarthi
    Commented Aug 26, 2022 at 20:42
  • 1
    $\begingroup$ This permanent may well be zero while maximal matchings always exist $\endgroup$
    – Fedor Petrov
    Commented Aug 27, 2022 at 7:21

0

Reset to default

You must log in to answer this question.