MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 Another reference

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, 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.
show/hide this revision's text 2 Trying to display images ...

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.
show/hide this revision's text 1

Local complementation in undirected graphs

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?