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

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.

Progress summary

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

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

1 week ago

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.

0 endorsements

Shivam Patel · 2 days ago