<p>Let $G=(V,E)$ be a graph having all the following restrictions:</p>

<ol>
<li>Every vertex $v \in V$ has degree $4$.</li>
<li>Every vertex $v \in V$ belongs to at least $2$ triangles.</li>
<li>For every vertex $v \in V$, if $v$ belongs to exactly $2$ triangles then such $2$ triangles do not share any edge.</li>
</ol>

<p>I would like to know whether such kind of graphs have been studied, what is known about them, and in particular which is the computational complexity of counting vertex covers and edge covers (even modulo $2$) on them. </p>

CC BY-SA 3.0
2013-06-12T09:22:05.280Z
The class of 4-regular $(K_{1,4}, \mathrm{cricket})$-free graphs is perhaps not the most well-studied.  :)   References: [4-regular](http://www.graphclasses.org/classes/gc_1101.html) [$K_{1,4}$-free](http://www.graphclasses.org/classes/gc_388.html) [cricket](http://www.graphclasses.org/smallgraphs.html#cricket)-free).
John K.
CC BY-SA 3.0
2013-06-12T18:21:42.073Z
@PålGD: Perhaps... ;-)
Giorgio Camerani
CC BY-SA 3.0
2013-06-12T21:41:01.450Z
I've just realized that the graph class I'm interested in is actually more specific. I've edited the question accordingly, by adding a third restriction. Such additional restriction corresponds to being dart-free (http://www.graphclasses.org/smallgraphs.html#dart).
Giorgio Camerani
<graph-theory><counting-complexity>
How hard is counting vertex covers / edge covers on the following graph class?
Giorgio Camerani
# How hard is counting vertex covers / edge covers on the following graph class?

(Asked by: username_0 on 2013-06-11)

Let $G=(V,E)$ be a graph having all the following restrictions:

1. Every vertex $v \in V$ has degree $4$.
2. Every vertex $v \in V$ belongs to at least $2$ triangles.
3. For every vertex $v \in V$, if $v$ belongs to exactly $2$ triangles then such $2$ triangles do not share any edge.

I would like to know whether such kind of graphs have been studied, what is known about them, and in particular which is the computational complexity of counting vertex covers and edge covers (even modulo $2$) on them.

**Tags:** graph-theory, counting-complexity

> **Comments:**
> **username_1**: The class of 4-regular $(K_{1,4}, \mathrm{cricket})$-free graphs is perhaps not the most well-studied.  :)   References: [4-regular](http://www.graphclasses.org/classes/gc_1101.html) [$K_{1,4}$-free](http://www.graphclasses.org/classes/gc_388.html) [cricket](http://www.graphclasses.org/smallgraphs.html#cricket)-free).  
> **username_0**: @PålGD: Perhaps... ;-)  
> **username_0**: I've just realized that the graph class I'm interested in is actually more specific. I've edited the question accordingly, by adding a third restriction. Such additional restriction corresponds to being dart-free (http://www.graphclasses.org/smallgraphs.html#dart).  

---

## 0 answers

