Let n_1≥…≥ n_k≥ 2 and m_1≥…≥ m_k≥ 2. Let T_1=T(n_1,…,n_k) and T_2=T(m_1,…,m_k) be starlike trees of order n and maximum degree k. For nonincreasing tuples, write (n_1,…,n_k)succ(m_1,…,m_k) when the first unequal coordinate of the first tuple is larger. Fixed-degree starlike-tree conjecture. (n_1,…,n_k)succ(m_1,…,m_k) if and only if T(m_1,…,m_k)succ T(n_1,…,n_k). This is the proposed total ordering of the fixed-order, fixed-maximum-degree family of starlike trees. The paper proves the conjecture for the family of starlike trees in the surrounding discussion, so the conjecture is presented as a target whose resolution should be checked against the paper's later results.

The total-order conjecture for fixed-degree starlike trees

About 13 years old · traced to 2013

Let $n_1\geq\cdots\geq n_k\geq 2$ and $m_1\geq\cdots\geq m_k\geq 2$ . Let $T_1=T(n_1,\ldots,n_k)$ and $T_2=T(m_1,\ldots,m_k)$ be starlike trees of order $n$ and maximum degree $k$ . For nonincreasing tuples, write $(n_1,\ldots,n_k)\succ(m_1,\ldots,m_k)$ when the first unequal coordinate of the first tuple is larger. Fixed-degree starlike-tree conjecture.

(n_1,\ldots,n_k)\succ(m_1,\ldots,m_k)

if and only if

T(m_1,\ldots,m_k)\succ T(n_1,\ldots,n_k).

This is the proposed total ordering of the fixed-order, fixed-maximum-degree family of starlike trees. The paper proves the conjecture for the family of starlike trees in the surrounding discussion, so the conjecture is presented as a target whose resolution should be checked against the paper's later results.

References

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).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A posted computation claims the conjecture is false at order $10$ and degree $3$ , but the counterexample has not been independently verified.

Oboudi’s 2013 paper formulates the conjecture that lexicographic comparison of branch-length tuples exactly reverses the independence-polynomial order of fixed-order starlike trees. It proves a weaker majorization implication and leaves the converse total-order statement as a conjecture.

Known results

Oboudi (2013): if one branch tuple majorizes another, the corresponding starlike trees satisfy the stated independence-polynomial order.

Posted attempt

A reader claims a complete disproof using $T(6,3,3)$ and $T(5,5,2)$ , whose independence polynomials allegedly differ by $x^4(1+3x)$ ; this reverses the conjectured comparison. The calculation is not independently verified.

Current status (as of August 2026): Oboudi’s majorization implication is established, while the proposed total-order equivalence has an unverified counterexample claim and therefore is not resolved.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

The proposed lexicographic characterization is false. Take the two starlike trees

T_a=T(6,3,3),\qquad T_b=T(5,5,2).

Both have $6+3+3-3+1=5+5+2-3+1=10$ vertices and maximum degree $3$ , while

(6,3,3)>_{\mathrm{lex}}(5,5,2).

Thus the conjecture predicts $T_b\succ T_a$ .

Let $P_j(x)$ denote the independence polynomial of a path on $j$ vertices. Then

P_0=1,\qquad P_1=1+x,\qquad P_j=P_{j-1}+xP_{j-2}.

Conditioning on whether the central vertex is selected gives

I(T(c_1,c_2,c_3),x) =\prod_{i=1}^{3}P_{c_i-1}(x) +x\prod_{i=1}^{3}P_{c_i-2}(x).

Consequently,

\begin{aligned} I(T_a,x)&=1+10x+36x^2+57x^3+38x^4+7x^5,\\ I(T_b,x)&=1+10x+36x^2+57x^3+39x^4+10x^5, \end{aligned}

and hence

I(T_b,x)-I(T_a,x)=x^4(1+3x). \tag{1}

Moreover,

I(T_a,-1/3)=-1/243<0,\qquad I(T_a,-1/4)=1/1024>0.

The intermediate-value theorem therefore gives a real root in $(-1/3,-1/4)$ . In particular, the largest real root $\xi(T_a)$ satisfies

\xi(T_a)>-1/3.

It follows from (1) that

I(T_b,x)>I(T_a,x)\qquad\text{for }\xi(T_a)\leq x<0.

By the definition of the independence-polynomial order, this says

T_a\succ T_b,

which is the exact opposite of the conjectured implication from $(6,3,3)>_{\mathrm{lex}}(5,5,2)$ . Therefore the proposed equivalence fails already for ten-vertex, degree-three starlike trees.