The extremal complement conjecture for independent and connected sets
The extremal complement conjecture for independent and connected sets
Let be a positive integer and let satisfy
For a graph , write for its number of independent sets, for its number of connected sets, and for its number of dominating connected sets. Let denote the complete graph on vertices. Extremal complement conjecture. Among all -regular graphs of order , for each of , , and , a maximizing graph is the complement of one or more copies of together with a graph satisfying
The graph 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 ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.