3
$\begingroup$

Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:

  • It has no isolated vertices.
  • It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).

Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j < i$.

Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.

I'm interested in $0$ obstructed vertex induced subgraphs.

Questions

  1. Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.
  2. If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?
  3. If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?

I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.

Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.

Improve this question
$\endgroup$
4
  • $\begingroup$ Maybe I miss something, but I think every induced subgraph of a complete graph is 0 obstructed, i.e., $N$ is not polynomially bounded. $\endgroup$
    – Marc Bury
    May 24, 2013 at 13:34
  • $\begingroup$ @MarcGillé: You are absolutely right in saying that my conjecture fails with the complete graph. However, such class is trivial and thus uninteresting. Let us focus on non trivial classes (by non trivial I mean those where computing $N$ is non trivial), like $3$-regular graphs. I've clarified the beginning of the question accordingly. $\endgroup$
    – Giorgio Camerani
    May 24, 2013 at 13:56
  • $\begingroup$ I presume you mean with your second condition that for the induced subgraph $G[V']$ (where $V' \subseteq V$), there should be some $V'' \supseteq V'$ such that $|V''| = |V'| + i$ and the induced subgraph $G[V'']$ contains the same edges as $G[V']$? $\endgroup$
    – András Salamon
    May 25, 2013 at 14:40
  • $\begingroup$ @AndrásSalamon: Exactly, you are right. $\endgroup$
    – Giorgio Camerani
    May 25, 2013 at 16:29

1 Answer 1

Reset to default
4
$\begingroup$

Sorry this is too long for a comment :)

Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs.

I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.