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

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

where

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

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

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

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

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

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

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.