4
$\begingroup$

Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties:

  • Their corresponding vertex induced subgraph has an even number of edges.
  • Their corresponding vertex induced subgraph has no isolated vertices.

Questions

  1. Did anyone already study the problem of computing $C_{E,0}$? What is known about it?
  2. More importantly, which is the computational complexity of computing $C_{E,0}\ mod\ 2$?
$\endgroup$

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.