The extremal inverse sum indegree energy conjecture for trees

Conjecture 1 of Hafeez and Farooq, Inverse Sum Indeg Energy of Graphs (IEEE Access 7 (2019), 100860–100866; arXiv:1905.03948), asserts that among all trees on $n$ vertices the path $P_n$ maximizes inverse-sum-indegree energy. We disprove this at $n=7$ and construct infinitely many counterexamples.

For a graph $G$, write $d_v$ for vertex degrees and define its symmetric inverse-sum-indegree matrix and energy by

$$S(G)_{uv}= \begin{cases} \dfrac{d_ud_v}{d_u+d_v},&uv\in E(G),\\ 0,&uv\notin E(G), \end{cases} \qquad \mathcal E_{\mathrm{ISI}}(G)=\lVert S(G)\rVert_*. \tag{1}$$

Let $T$ consist of a central vertex joined to three internally disjoint paths of length two. Its three center-to-intermediate edges have weight $6/5$, and its three intermediate-to-leaf edges have weight $2/3$. Direct decomposition into symmetric and antisymmetric arm subspaces gives

$$\det(xI-S(T)) =x\left(x^2-\frac49\right)^2 \left(x^2-\frac{1072}{225}\right), \qquad \mathcal E_{\mathrm{ISI}}(T) =\frac{40+8\sqrt{67}}{15}. \tag{2}$$

For the seven-vertex path, the two end edges have weight $2/3$ and all other edges have weight $1$. Its tridiagonal determinant is

$$\det(xI-S(P_7)) =\frac{x(9x^2-13)(9x^4-31x^2+8)}{81}. \tag{3}$$

Adding its positive eigenvalues and combining the two quadratic radical terms gives

$$\mathcal E_{\mathrm{ISI}}(P_7) =\frac23\left(\sqrt{13}+\sqrt{31+12\sqrt2}\right). \tag{4}$$

All comparisons can be certified rationally. Squaring positive quantities gives

$$\sqrt{13}<\frac{361}{100}, \qquad \sqrt2<\frac{99}{70}, \qquad \frac{1679}{35}<\left(\frac{693}{100}\right)^2, \qquad \sqrt{67}>\frac{327}{40}. \tag{5}$$

Consequently,

$$\mathcal E_{\mathrm{ISI}}(P_7) <\frac23\left(\frac{361}{100}+\frac{693}{100}\right) =\frac{527}{75} <\frac{40+8\sqrt{67}}{15} =\mathcal E_{\mathrm{ISI}}(T). \tag{6}$$

We next prove that failures occur at arbitrarily large orders. For $k\geq1$, construct a tree $C_k$ from a $k$-vertex spine by attaching one length-two pendant arm at every spine vertex and one additional length-two arm at each end of the spine. When $k=1$, the two ends coincide, so the single spine vertex receives three arms. Every spine vertex has degree $3$, and

$$|V(C_k)|=3k+4. \tag{7}$$

Delete the four vertices of the two additional end arms, taking the principal submatrix rather than recomputing degrees. After grouping spine, intermediate, and leaf vertices, the resulting $3k\times3k$ matrix is

$$B_k= \begin{pmatrix} \frac32A(P_k)&\frac65I_k&0\\ \frac65I_k&0&\frac23I_k\\ 0&\frac23I_k&0 \end{pmatrix}. \tag{8}$$

Trace-norm contraction under orthogonal compression implies

$$\mathcal E_{\mathrm{ISI}}(C_k)\geq\lVert B_k\rVert_*. \tag{9}$$

Diagonalizing $A(P_k)$ by the discrete sine transform reduces $B_k$ to the orthogonal direct sum of

$$J(\theta_j)= \begin{pmatrix} \theta_j&6/5&0\\ 6/5&0&2/3\\ 0&2/3&0 \end{pmatrix}, \qquad \theta_j=3\cos\left(\frac{j\pi}{k+1}\right), \quad 1\leq j\leq k. \tag{10}$$

For $0\leq\theta\leq3$, the unique negative eigenvalue of $J(\theta)$ is $-z(\theta)$, where $z(\theta)>0$ is the unique positive root of

$$F_\theta(z) =z^3+\theta z^2-\frac{424}{225}z-\frac49\theta. \tag{11}$$

Substituting $z_0=23/20-\theta/10$ yields

$$72000F_\theta(z_0) =648\theta^3-14076\theta^2+48222\theta-46529 =648u^3-10188u^2-306u-1205, \qquad u=\theta-2. \tag{12}$$

If $0\leq u\leq1$, use $u^3\leq u^2$ to see that the last expression is negative. If $-2\leq u\leq0$, put $v=-u$; it becomes

$$-648v^3-10188v^2+306v-1205 \leq612-1205<0. \tag{13}$$

Since $F_\theta$ has exactly one positive root, this proves

$$z(\theta)>\frac{23}{20}-\frac{\theta}{10}. \tag{14}$$

The trace of $J(\theta)$ is $\theta$, so its energy is $\theta+2z(\theta)$. Also $J(-\theta)$ is orthogonally similar to $-J(\theta)$. Therefore

$$\lVert J(\theta)\rVert_* >\frac{23}{10}+\frac45|\theta|, \qquad -3\leq\theta\leq3. \tag{15}$$

For even $k$, the elementary finite cosine sum and $\sin x<x$ give

$$\begin{aligned} \mathcal E_{\mathrm{ISI}}(C_k) &>\frac{23k}{10} +\frac{12}{5}\sum_{j=1}^k \left|\cos\left(\frac{j\pi}{k+1}\right)\right|\\ &=\frac{23k}{10} +\frac{12}{5}\left( \csc\left(\frac{\pi}{2(k+1)}\right)-1\right)\\ &>\frac{23k}{10}+\frac{24(k+1)}{5\pi}-\frac{12}{5}. \end{aligned} \tag{16}$$

Put $n=3k+4$, which is even. The inverse-sum-indegree path matrix factors as

$$S(P_n)=D A(P_n)D, \qquad D=\operatorname{diag}\left(\frac23,1,\ldots,1,\frac23\right). \tag{17}$$

Since $\lVert D\rVert\leq1$, trace-norm contraction and the exact ordinary-path energy formula show that

$$\mathcal E_{\mathrm{ISI}}(P_n) \leq\lVert A(P_n)\rVert_* =2\left(\csc\left(\frac{\pi}{2(n+1)}\right)-1\right) <\frac{4(n+1)}{\pi}. \tag{18}$$

For the last inequality, set $x=\pi/(2(n+1))<1$ and use $\sin x>x-x^3/6>x/(1+x)$.

Finally, the classical rational bounds $157/50<\pi<22/7$ give

$$\begin{aligned} \mathcal E_{\mathrm{ISI}}(C_k) -\mathcal E_{\mathrm{ISI}}(P_{3k+4}) &>\frac{23k}{10}+\frac{84(k+1)}{55} -\frac{12}{5}-\frac{200(3k+5)}{157}\\ &=\frac{97k-125072}{17270}>0 \qquad\text{for every even }k\geq1290. \end{aligned} \tag{19}$$

Thus the path-maximality assertion fails already on seven vertices and for infinitely many trees of maximum degree three. The separate assertion that the star minimizes inverse-sum-indegree energy is not addressed here.