The extremal complement conjecture for independent and connected sets

Let dd be a positive integer and let nn satisfy

d+1n2d.d+1\le n\le 2d.

For a graph GG, write i(G)i(G) for its number of independent sets, N(G)N(G) for its number of connected sets, and Ndom(G)N_{dom}(G) for its number of dominating connected sets. Let KndK_{n-d} denote the complete graph on ndn-d vertices. Extremal complement conjecture. Among all dd-regular graphs of order nn, for each of i(G)i(G), N(G)N(G), and Ndom(G)N_{dom}(G), a maximizing graph is the complement of one or more copies of KndK_{n-d} together with a graph HH satisfying

H<2(nd).\lvert H\rvert<2(n-d).

The graph HH may depend on which quantity is being maximized. This conjecture is presented as an analogue of an earlier conjecture concerning the number of cliques in complements. It predicts a common extremal structure for three graph-counting problems in the range d+1n2dd+1\le n\le 2d; the source supplies no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Jan Goedgebeur and Jorik Jooken, “The maximum number of connected sets in regular graphs”, arXiv:2311.00075 (2024).

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.