Timeline for Smallest odd cycle in a non-bipartite graph
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 10, 2019 at 22:07 | comment | added | Alex Meiburg | @GerryMyerson I appreciate the recommendation, but cage graphs also avoid small even cycles. I did search for "odd cages" or something, but without success. | |
| Apr 10, 2019 at 22:03 | comment | added | Gerry Myerson | oeis.org/A054760 Table $T(n,k) =$ order of $(n,k)$-cage (smallest $n$-regular graph of girth $k$), $n \ge 2$, $k \ge 3$, read by antidiagonals. | |
| Apr 10, 2019 at 22:01 | comment | added | Gerry Myerson | "In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an $(r,g)$-graph is defined to be a graph in which each vertex has exactly $r$ neighbors, and in which the shortest cycle has length exactly $g$." (quoting Wikipedia). So maybe you want to check out the literature on "cage graphs". | |
| Apr 10, 2019 at 21:55 | answer | added | Ilya Bogdanov | timeline score: 6 | |
| Apr 10, 2019 at 21:37 | comment | added | Ilya Bogdanov | We can do better. Take a cycle of length $6k+3$, enumerate its vertices consecutively, and duplicate those with numbers not divisible by 3. You get $10k+5$ vertices, so a cycle is of length $3n/5$. | |
| Apr 10, 2019 at 21:32 | comment | added | Ilya Bogdanov | To add a vertex, just make a copy of an existing one | |
| Apr 10, 2019 at 20:03 | comment | added | Alex Meiburg | I'm not sure how to prove it either, but that sounds probably tight. For n=4m+2 that gives at least 2m+1=n/2. For other values of n mod 4, I'm now thinking any ways to add a vertex or two to that construction. For n=4m+3, 4m+4 or 4m+5 I see how to still get k≥2m+1 (with modifications not worth describing in a comment) but I'm much less confident those would be tight. | |
| Apr 10, 2019 at 19:48 | comment | added | Florian Lehner | The shortest odd cycle in the Cartesian product of $C_k$ and $K_2$ for odd $k$ contains half of the vertices, not sure if that's best possible though. | |
| Apr 10, 2019 at 19:25 | history | asked | Alex Meiburg | CC BY-SA 4.0 |