# Number of Vertex Covers and Permanent

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

• Perhaps you could explain why you believe that these should be related? Do you have any evidence that supports this belief? – Jukka Suomela Sep 15 '10 at 13:25
• 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. – Tsuyoshi Ito Sep 15 '10 at 13:43
• @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. – Giorgio Camerani Sep 15 '10 at 13:51
• maybe you wanted a relationship between the number of vertex cycle covers and the permanent, which they are equal. – didest Sep 15 '10 at 15:59

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.