Generalisation of the frustrated-triangle extremal conjecture to frustrated cycles

Let GG be a graph, let G\overline{G} denote its complement, and for k3k\geq 3 let fk(G)f_k(G) be the number of frustrated kk-cycles, where a cyclic ordering v1v2vkv_1v_2\dots v_k is frustrated when an odd number of its consecutive cycle edges belongs to GG. For integers t0t\geq 0, let a (t+1)(t+1)-star on nn vertices be the graph consisting of a star with t+1t+1 leaves together with the remaining isolated vertices. Frustrated-cycle generalisation conjecture. For every k3k\geq 3, t0t\geq 0, and all sufficiently large nn, if

fk(G)<fk((t+1)-star on n vertices),f_k(G)<f_k\big((t+1)\text{-star on }n\text{ vertices}\big),

then either GG or G\overline{G} can be obtained from a complete bipartite graph by flipping at most tt edges or non-edges. This proposes an extension of the paper's structural result for frustrated triangles to frustrated cycles; its resolution is not given in the source.

Sources & referencesView supporting material

Primary source

Teeradej Kittipassorn and Gabor Meszaros, “Frustrated Triangles”, arXiv:1411.1749 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.