Fuller–Gould conjecture on dense K4K_4^--saturated graphs

Let K4K_4^- be the graph obtained from the complete graph K4K_4 by deleting one edge. A graph is K4K_4^--saturated if it contains no copy of K4K_4^-, but adding any missing edge creates at least one copy of K4K_4^-. Write [a,b]={a,a+1,,b}[a,b]=\{a,a+1,\ldots,b\}.

Fuller–Gould conjecture. The K4K_4^--saturated graphs with sizes in the interval

[n2n2n+7,n2n2]\left[\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil-n+7,\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{n}{2}\right\rceil\right]

are of two types: complete bipartite graphs with partite sets of nearly equal size, and 3-partite graphs with two partite sets of nearly equal size and one partite set of order one.

This conjecture describes the structure of K4K_4^--saturated graphs whose numbers of edges are close to the extremal value n/2n/2\left\lfloor n/2\right\rfloor\left\lceil n/2\right\rceil. The cited work establishes the preceding range of edge sizes up to one below the interval's lower endpoint, while the proposed structural classification for this dense range is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Jun Gao, Xinmin Hou and Yue Ma, “The edge spectrum of K_4^--saturated graphs”, arXiv:1804.10359 (2018).

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.