The minimum maximal-independent-set conjecture for connected twin-free triangle-free graphs

About 4 years old · traced to

Let GG be a connected, twin-free and triangle-free graph of order nn. Write imax(G)i_{\text{max}}(G) for the number of maximal independent sets of GG. Minimum maximal-independent-set conjecture.

imax(G)≥⌈n2⌉+1.i_{\text{max}}(G) \ge \left\lceil\frac{n}{2}\right\rceil+1.

Furthermore, if nn is even, every graph attaining equality is bipartite. The preceding theorem proves this bound for connected twin-free bipartite graphs, while the extension to triangle-free graphs is presented as unproved; the equality characterization is likewise part of the conjecture.

References

Primary source

Stijn Cambie and Stephan Wagner, “The minimum number of maximal independent sets in twin-free graphs”, arXiv:2211.04357 (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.