Problem statement

Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:

1. complementing the subgraph induced by $v$ and its neighbours,
2. flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
3. removing $v$ from $V$.

The goal is to delete the whole graph using only local complementations.

Questions

Given an ordering $\mathcal O$ of the vertices of $V$, can we characterise cases in which $\mathcal O$ allows us (or not) to delete $G$?

##Comments##

A lot of work on local complementations (or "vertex eliminations" in some papers) concerns itself with algorithmic issues, especially with finding orderings that will work. Note that this differs from my question, since here you don't get to choose an ordering.

Of course, verifying whether an ordering works is easy: keep complementing until you're done or stuck. Finding necessary or sufficient nontrivial structural conditions on $G$ or $\mathcal O$ seems harder. Does this problem ring any bell?

##Example##

Two different orderings for the same graph; the first one does not work:

The second one does:

References

The only mention of this exact problem I've found so far is Hannenhalli and Pevzner, starting from page 14. All other authors (e.g. Sabidussi) consider variants like using directed graphs, or non-coloured vertices, or complementations which do not modify edges adjacent to $v$. Other authors whose papers I'm currently looking into are Donald J. Rose, Robert Endre Tarjan and François Genest.

Problem statement

Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:

1. complementing the subgraph induced by $v$ and its neighbours,
2. flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
3. removing $v$ from $V$.

The goal is to delete the whole graph using only local complementations.

Questions

Given an ordering $\mathcal O$ of the vertices of $V$, can we characterise cases in which $\mathcal O$ allows us (or not) to delete $G$?

##Comments##

A lot of work on local complementations (or "vertex eliminations" in some papers) concerns itself with algorithmic issues, especially with finding orderings that will work. Note that this differs from my question, since here you don't get to choose an ordering.

Of course, verifying whether an ordering works is easy: keep complementing until you're done or stuck. Finding necessary or sufficient nontrivial structural conditions on $G$ or $\mathcal O$ seems harder. Does this problem ring any bell?

##Example##

Two different orderings for the same graph; the first one does not work:

The second one does:

References

Hannenhalli and Pevzner, starting from page 14, and Hartman and Verbin. All other authors (e.g. Sabidussi) consider variants like using directed graphs, or non-coloured vertices, or complementations which do not modify edges adjacent to $v$. Other authors whose papers I'm currently looking into are Donald J. Rose, Robert Endre Tarjan and François Genest.

Problem statement

Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:

1. complementing the subgraph induced by $v$ and its neighbours,
2. flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
3. removing $v$ from $V$.

The goal is to delete the whole graph using only local complementations.

Questions

Given an ordering $\mathcal O$ of the vertices of $V$, can we characterise cases in which $\mathcal O$ allows us (or not) to delete $G$?

##Comments##

A lot of work on local complementations (or "vertex eliminations" in some papers) concerns itself with algorithmic issues, especially with finding orderings that will work. Note that this differs from my question, since here you don't get to choose an ordering.

Of course, verifying whether an ordering works is easy: keep complementing until you're done or stuck. Finding necessary or sufficient nontrivial structural conditions on $G$ or $\mathcal O$ seems harder. Does this problem ring any bell?

Problem statement

Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:

1. complementing the subgraph induced by $v$ and its neighbours,
2. flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
3. removing $v$ from $V$.

The goal is to delete the whole graph using only local complementations.

Questions

Given an ordering $\mathcal O$ of the vertices of $V$, can we characterise cases in which $\mathcal O$ allows us (or not) to delete $G$?

##Comments##

A lot of work on local complementations (or "vertex eliminations" in some papers) concerns itself with algorithmic issues, especially with finding orderings that will work. Note that this differs from my question, since here you don't get to choose an ordering.

Of course, verifying whether an ordering works is easy: keep complementing until you're done or stuck. Finding necessary or sufficient nontrivial structural conditions on $G$ or $\mathcal O$ seems harder. Does this problem ring any bell?

##Example##

Two different orderings for the same graph; the first one does not work:

The second one does:

References

The only mention of this exact problem I've found so far is Hannenhalli and Pevzner, starting from page 14. All other authors (e.g. Sabidussi) consider variants like using directed graphs, or non-coloured vertices, or complementations which do not modify edges adjacent to $v$. Other authors whose papers I'm currently looking into are Donald J. Rose, Robert Endre Tarjan and François Genest.