2
$\begingroup$

Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?

$\endgroup$
  • 1
    $\begingroup$ Perhaps you could explain why you believe that these should be related? Do you have any evidence that supports this belief? $\endgroup$ – Jukka Suomela Sep 15 '10 at 13:25
  • $\begingroup$ To me, this question sounds just arbitrary. We could ask any questions of the form “How are X and Y related?” but we should not do that. See this discussion on meta, especially this answer and this answer. Although it is an ongoing discussion, I think that these answers are pretty reasonable. $\endgroup$ – Tsuyoshi Ito Sep 15 '10 at 13:43
  • $\begingroup$ @Jukka, Tsuyoshi: I have no evidence that they should be related, I was simply asking. Sorry, the question was badly written, I've modified it. $\endgroup$ – Giorgio Camerani Sep 15 '10 at 13:51
  • $\begingroup$ maybe you wanted a relationship between the number of vertex cycle covers and the permanent, which they are equal. $\endgroup$ – Diego de Estrada Sep 15 '10 at 15:59
12
$\begingroup$

If $G$ has an isolated node, the permanent will be equal to 0.

If you know that permanent is 0, it tells extremely little about the number of vertex covers in $G$. You can take any graph $G$ and construct $G'$ by adding an isolated node; the number of vertex covers in $G'$ is exactly 2 times the number of vertex covers in $G$ – which can be virtually anything – while the permanent of $G'$ is 0.

Conversely, if you know the number of vertex covers, you can't tell if the permanent is 0 or not. For example, you can take any graph $G$ with a non-zero permanent and construct two new graphs: $G_1$ is $G$ + a triangle, and $G_2$ is $G$ + two isolated nodes. Both $G_1$ and $G_2$ have exactly 4 times as many vertex covers as $G$. However, $G_1$ will have a non-zero permanent while $G_2$ will have permanent 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.