Timeline for Local complementation in undirected graphs
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2010 at 23:37 | vote | accept | Anthony Labarre | ||
| Mar 2, 2010 at 19:38 | history | edited | Anthony Labarre | CC BY-SA 2.5 |
Another reference
|
| Feb 28, 2010 at 9:46 | answer | added | domotorp | timeline score: 4 | |
| Feb 28, 2010 at 9:03 | comment | added | Anthony Labarre | No problem. Yes, in this case you can remove the graph, so I was wrong. The examples I've been working on satisfy the following additional condition, which I should have mentioned: white (resp. black) vertices have an even (resp. odd) number of neighbours. But maybe your next comment will prove me wrong again? ;-) | |
| Feb 28, 2010 at 7:42 | comment | added | domotorp | Indeed, I forgot about that. But let me ask another stupid question (I promise to delete these comments once I got it) - What if A is a single vertex and B is on edge? In this case calling the vertices according to their order, 1 is connected to both 2 and 3 and the black vertices are 1 and 3. Seems to me that the whole graph gets deleted. | |
| Feb 27, 2010 at 22:17 | comment | added | Anthony Labarre | No, at least one of $b$'s neighbours will become black and will become connected to $a$. | |
| Feb 27, 2010 at 19:54 | comment | added | domotorp | I am not sure that I understand what you mean. If we start with b then a will be colored white and A will be disconnected from B, so there seems to be no way to continue. | |
| Feb 27, 2010 at 16:20 | answer | added | Joe Fitzsimons | timeline score: 4 | |
| Feb 27, 2010 at 12:42 | comment | added | Anthony Labarre | Gerhard: sorry if I'm not clear, let me try to fix that. The ordering is total, and you are supposed to act on vertex 1, then vertex 2, and so on. I added an example which I hope helps to understand the process. One example of a conjecture: build a graph $G$ by taking two connected components $A$ and $B$ which contain exactly one black vertex each (namely, $a$ in $A$ and $b$ in $B$) and adding an edge connecting $a$ and $b$. Then no ordering that starts with vertex $b$ and uses all vertices in $B$ before those in $A$ will work. domotorp: I added some info. | |
| Feb 27, 2010 at 12:37 | history | edited | Anthony Labarre | CC BY-SA 2.5 |
Trying to display images ...
|
| Feb 27, 2010 at 0:40 | comment | added | Gerhard Paseman | It would help if you were clear on the relationship of the order to the process. For example, I do not know if O is total or partial. I also do not know if O means start with the least or the greatest vertex in doing local complementation. Further, it seems that the coloring of the vertices has as much or more to do with the problem than the adjacency, so you may only get characterizations of pairs (O,C), unless the coloring C is strongly tied to the graph. Also, a conjecture on what characterization you think might hold would help. Gerhard "Ask Me About System Design" Paseman, 2010.02.26 | |
| Feb 26, 2010 at 22:31 | comment | added | domotorp | Could you give some references to the papers? | |
| Feb 26, 2010 at 17:53 | comment | added | Anthony Labarre | Yes, because at any given step, you can only select black vertices. So graphs with only white vertices are examples of graphs that cannot be deleted. | |
| Feb 26, 2010 at 17:19 | comment | added | Hsien-Chih Chang 張顯之 | Does the initial condition for the color of the vertices makes any difference? | |
| Feb 26, 2010 at 16:38 | history | asked | Anthony Labarre | CC BY-SA 2.5 |