ON GENERALIZED DISTANCE SPECTRAL RADIUS OF A BIPARTITE GRAPH

NEW

Problem: The literal statement (“among all trees”) is false without fixing the order: for paths $P_n$, the generalized distance spectral radius is unbounded as $n\to\infty$.

The natural repaired statement is:

For fixed $n\ge2$ and $0<\alpha\le1$, among all trees $T$ on $n$ vertices, the unique tree maximizing the generalized distance spectral radius

$$\rho_\alpha(T)=\rho(D_\alpha(T)),\qquad D_\alpha(T)=\alpha \operatorname{Tr}(T)+(1-\alpha)D(T),$$

where $D(T)$ is the distance matrix and $\operatorname{Tr}(T)=\operatorname{diag}(\operatorname{Tr}_T(v))$, is the path $P_n$.

Result: The repaired statement is true: $P_n$ is the unique maximizer.

Proof sketch with full key argument. For $0<\alpha<1$, let $T$ be a maximizing tree and let $x>0$ be the Perron unit eigenvector of $D_\alpha(T)$. Then

$$x^{\top}D_\alpha(T)x = \sum_{\{u,v\}\subseteq V(T)} d_T(u,v)\,w_{uv},$$

where

$$w_{uv}=\alpha(x_u^2+x_v^2)+2(1-\alpha)x_ux_v>0.$$

We use the following elementary lemma.

Lemma. Let $w_{uv}>0$ be positive symmetric pair-weights on a fixed vertex set. Among all trees on that vertex set, any tree maximizing

$$\sum_{\{u,v\}} w_{uv}d_T(u,v)$$

must be a path.

Proof. Suppose a maximizing tree $T$ has a vertex $z$ of degree at least $3$. Removing $z$ gives components $B_1,\dots,B_k$, $k\ge3$. For $i\ne j$, form $T_{i\to j}$ by deleting the edge from $z$ to $B_i$ and attaching $B_i$ to the neighbor of $z$ in $B_j$. Distances from $B_i$ to $B_j$ decrease by $1$, while distances from $B_i$ to every vertex outside $B_i\cup B_j$ increase by $1$. Thus maximality gives

$$W(B_i,V\setminus(B_i\cup B_j))\le W(B_i,B_j),$$

where $W(A,B)=\sum_{a\in A,b\in B}w_{ab}$. Fixing $i$, this implies $W(B_i,B_j)\ge \frac12 W(B_i,V\setminus B_i)$ for every $j\ne i$. Taking two distinct such $j$’s is impossible because $z\in V\setminus B_i$ and all weights are positive. Contradiction. Hence $\Delta(T)\le2$, so $T$ is a path. ∎

Applying the lemma to the weights $w_{uv}$, any non-path maximizer $T$ can be replaced by a tree $T'$ with

$$x^{\top}D_\alpha(T')x>x^{\top}D_\alpha(T)x=\rho_\alpha(T),$$

so $\rho_\alpha(T')>\rho_\alpha(T)$, contradiction. Hence $T=P_n$.

For $\alpha=1$, $D_1(T)=\operatorname{Tr}(T)$ is diagonal, so

$$\rho_1(T)=\max_v \operatorname{Tr}_T(v).$$

For any vertex $v$ in an $n$-vertex tree,

$$\operatorname{Tr}_T(v)\le 1+2+\cdots+(n-1)=\frac{n(n-1)}2,$$

with equality iff there is exactly one vertex at each distance $1,\dots,n-1$ from $v$, i.e. iff $T=P_n$ and $v$ is an endpoint. Thus $P_n$ is again the unique maximizer.

Citation: No external citation used; the proof above gives the resolution.