← All problems

Caterpillar conjecture for block graphs maximizing mean CIS order

8 years old · traced to

Let n≥5n\geq 5, and let GG be a block graph of order nn. Suppose that GG has maximum mean CIS order among all block graphs of order nn. Block-graph caterpillar conjecture. Then GG is a caterpillar. This strengthens Jamison's Caterpillar Conjecture from trees to block graphs. The claim has been verified for 5≤n≤115\leq n\leq 11, but the general case remains open.

References
  1. Kristaps J. Balodis, Matthew E. Kroeker, Lucas Mol and Ortrud R. Oellermann, “On the Mean Order of Connected Induced Subgraphs of Block Graphs”, arXiv:1811.05430 (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.