Timeline for How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2014 at 4:09 | vote | accept | GMB | ||
| Feb 11, 2014 at 23:14 | comment | added | The Masked Avenger | I think it is also intended that for every edge, that edge belongs to a cycle, and the minimum of the girths of all cycles containing that edge is k, and this holds for all edges. | |
| Feb 11, 2014 at 21:51 | comment | added | Daniel Soltész | @GMB These are not equivalent definitions! One can construct a graph, such that every edge is in a chordless k-cycle (no proper subset of these $k$ vertices form a cycle) but the graph contains a triangle. | |
| Feb 11, 2014 at 21:17 | comment | added | GMB | By minimal $k$-cycle, I mean that no proper subset of the $k$ vertices forms a cycle. Another way of phrasing this question is "every edge belongs to a cycle, and the graph has girth $k$." | |
| Feb 11, 2014 at 17:03 | answer | added | The Masked Avenger | timeline score: 1 | |
| Feb 11, 2014 at 16:33 | comment | added | The Masked Avenger | I think a graph of girth k on n vertices is wanted. Also, for large k, any two such cycles have at most two links between them. Here a link is an edge off of both cycles that has a vertex on each cycle. | |
| Feb 11, 2014 at 9:13 | comment | added | Seva | What do you mean by a minimal $k$-cycle? | |
| Feb 11, 2014 at 8:00 | history | asked | GMB | CC BY-SA 3.0 |