ON THE LARGEST DISTANCE (SIGNLESS LAPLACIAN) EIGENVALUE OF NON-TRANSMISSION-REGULAR GRAPHS*

NEW

Problem: For a finite simple connected graph $G$ on $n$ vertices, let $\mathcal D=(d(u,v))$ be its distance matrix. Let

and let $\lambda_1(\mathcal D)$ be the Perron/largest eigenvalue of $\mathcal D$. The graph is transmission-regular if all $T(v)$ are equal. The reconstructed conjecture is:

If $G$ is connected and not transmission-regular, then

This matches the paper’s notation: $D_1$ is the maximum transmission degree and $\lambda_1(D)$ is the largest distance eigenvalue.

Result: The conjecture is true. In fact,

Proof. Put $\Delta=D_1$, and write $T_i=T(v_i)$. Since $\mathcal D$ is symmetric,

For $c_i=\Delta-T_i$, we have $c_i\in\mathbb Z_{\ge0}$, and because $G$ is not transmission-regular, some $c_i>0$. Also $d(v_i,v_j)\ge1$ for $i\ne j$. For any real vector $x$,

Let $S=\{i:c_i>0\}$, nonempty. Since $d(v_i,v_j)\ge1$ and $c_i\ge1$ on $S$,

Choosing $p\in S$, this gives the Loewner inequality

where $L(K_n)=nI-J$ is the Laplacian of the complete graph and $E_{pp}$ has a single $1$ in position $(p,p)$.

By symmetry take $p=1$. The smallest eigenvalue of

is computed on vectors $(a,b,\dots,b)$. The eigenvalue equations are

so

Hence

Therefore

Finally,

Thus

Verification audit: no extra graph-theoretic assumptions were added beyond finite, simple, connected, non-transmission-regular; the proof uses only standard distance-matrix facts and Rayleigh-Ritz; the strict conjectured inequality follows exactly.

Citation: No external citation used; proof supplied above.