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

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-15T13:24:31.470Z
2010-09-15T13:24:31.470Z
Jukka Suomela
<p>Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix? </p>

CC BY-SA 2.5
2010-09-15T13:25:33.953Z
Perhaps you could explain why you believe that these *should* be related? Do you have any evidence that supports this belief?
Jukka Suomela
CC BY-SA 2.5
2010-09-15T13:43:26.543Z
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](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), especially [this answer](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304) and [this answer](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306).  Although it is an ongoing discussion, I think that these answers are pretty reasonable.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-15T13:51:52.393Z
@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
CC BY-SA 2.5
2010-09-15T15:59:32.110Z
maybe you wanted a relationship between the number of vertex *cycle* covers and the permanent, which they are equal.
didest
<cc.complexity-theory><ds.algorithms><graph-theory>
Number of Vertex Covers and Permanent
Giorgio Camerani
# Number of Vertex Covers and Permanent

(Asked by: username_0 on 2010-09-15)

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

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory

> **Comments:**
> **username_1**: Perhaps you could explain why you believe that these *should* be related? Do you have any evidence that supports this belief?  
> **username_2**: 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](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), especially [this answer](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/304#304) and [this answer](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/306#306).  Although it is an ongoing discussion, I think that these answers are pretty reasonable.  
> **username_0**: @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.  
> **username_3**: maybe you wanted a relationship between the number of vertex *cycle* covers and the permanent, which they are equal.  

---

## 1 answers

### Answer by username_1 on 2010-09-15. Score: 12 | Accepted answer

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.


---

