The total-order conjecture for trees under the independence-polynomial order

Let \succeq be the order on graphs defined by comparing their independence polynomials, and let Tn\mathcal{T}_n be the set of trees with nn vertices. Total-order conjecture. For any two trees T1,T2TnT_1,T_2\in\mathcal{T}_n,

T1T2orT2T1.T_1\succeq T_2\quad\text{or}\quad T_2\succeq T_1.

The claim would make all trees of a fixed order comparable under this graph order. The paper notes that the order is not total on all graphs and gives partial ordering results for trees, but does not prove totality for all trees.

Sources & referencesView supporting material

Primary source

Mohammad Reza Oboudi, “On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike trees”, arXiv:1303.3222 (2013).

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.