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
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 17, 2016 at 17:45 | comment | added | Ilya Bogdanov | If by minimal cycles the OP means just induced ones, then the $k=4$ case has a better example, namely $K_{2,2,2,\dots,2}$ (or $K_{2,2,\dots,2,3}$ if $n$ is odd). OTOH, if a graph of girth $k$ is needed, then the optimality of a complete bipartite graph is confirmed by Turan's theorem. | |
| Feb 12, 2014 at 4:09 | vote | accept | GMB | ||
| Feb 11, 2014 at 19:19 | comment | added | The Masked Avenger | If you want to do more research, girth and cages are search terms I suggest. The Petersen graph should clue you in on why k=5 and 6 will require a different analysis. | |
| Feb 11, 2014 at 17:15 | history | edited | The Masked Avenger | CC BY-SA 3.0 |
edited body
|
| Feb 11, 2014 at 17:09 | comment | added | The Masked Avenger | This construction leads to a recurrence for a nice lower bound. Namely, view each k cycle as a point and each pair of links as an edge, and use a graph of girth k/2 and l points as a guide for linking the cycles. I would look over someone else's analysis using this idea with attribution. | |
| Feb 11, 2014 at 17:03 | history | answered | The Masked Avenger | CC BY-SA 3.0 |