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.

  • $\begingroup$ The class of 4-regular $(K_{1,4}, \mathrm{cricket})$-free graphs is perhaps not the most well-studied. :) References: 4-regular $K_{1,4}$-free cricket-free). $\endgroup$ – Pål GD Jun 12 '13 at 9:22
  • $\begingroup$ @PålGD: Perhaps... ;-) $\endgroup$ – Giorgio Camerani Jun 12 '13 at 18:21
  • $\begingroup$ 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 (graphclasses.org/smallgraphs.html#dart). $\endgroup$ – Giorgio Camerani Jun 12 '13 at 21:41

Your Answer

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

Browse other questions tagged or ask your own question.