Timeline for Cycles of length 1(mod 3) in regular graphs
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 27, 2010 at 14:44 | comment | added | Jukka Suomela | @David: I think you need to be a bit more careful in the construction of G; removing the articulation point may create new articulation points. I added a sketch of the construction of G above; essentially just do what you said, remove all bridges, and pick one of the components. | |
| Jul 27, 2010 at 14:37 | history | edited | Jukka Suomela | CC BY-SA 2.5 |
added construction of G
|
| Jul 27, 2010 at 3:14 | comment | added | David Eppstein | Finding your subgraph G is easy, as you say: if H is not biconnected, find a block with only one articulation point adjacent to it, and let G be the remaining vertices in that block. If H is biconnected, you can just use H in place of G, since you don't actually require the existence of the two degree-three vertices, but if you really want them you can remove the last ear in an ear decomposition. | |
| Jul 27, 2010 at 3:12 | vote | accept | Gjergji Zaimi | ||
| Jul 26, 2010 at 17:48 | history | answered | Jukka Suomela | CC BY-SA 2.5 |