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

$$T(v)=\sum_{u\in V(G)} d(u,v),\qquad D_1=\max_{v}T(v),$$

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

$$D_1-\lambda_1(\mathcal D)>\frac1{n+1}.$$

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,

$$D_1-\lambda_1(\mathcal D)\ge \alpha_n:=\frac{(n+1)-\sqrt{(n+1)^2-4}}2>\frac1{n+1}.$$

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

$$\Delta-\lambda_1(\mathcal D)=\lambda_{\min}(\Delta I-\mathcal D).$$

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$,

$$x^T(\Delta I-\mathcal D)x = \sum_{i<j} d(v_i,v_j)(x_i-x_j)^2+\sum_i c_i x_i^2.$$

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

$$x^T(\Delta I-\mathcal D)x \ge \sum_{i<j}(x_i-x_j)^2+\sum_{i\in S}x_i^2.$$

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

$$\Delta I-\mathcal D \succeq L(K_n)+E_{pp},$$

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

$$nI-J+E_{11}$$

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

$$na-(n-1)b=\lambda a,\qquad b-a=\lambda b,$$

so

$$\lambda^2-(n+1)\lambda+1=0.$$

Hence

$$\lambda_{\min}(nI-J+E_{11}) = \frac{(n+1)-\sqrt{(n+1)^2-4}}2 =\alpha_n.$$

Therefore

$$D_1-\lambda_1(\mathcal D)\ge \alpha_n.$$

Finally,

$$\alpha_n=\frac{2}{(n+1)+\sqrt{(n+1)^2-4}} > \frac{2}{2(n+1)} = \frac1{n+1}.$$

Thus

$$D_1-\lambda_1(\mathcal D)>\frac1{n+1}.$$

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.