Different central parts of trees and their pairwise distances

NEW

Problem: For finite simple trees, let the characteristic set be defined from a Fiedler vector of the Laplacian: a characteristic vertex has Fiedler coordinate $0$ with a nonzero neighbor, and a characteristic edge has endpoint coordinates of opposite signs. For a tree this set is independent of the Fiedler vector and is either one vertex or one edge.

Reconstructed conjecture: for every path-star tree $P_{n-g,g}$, $2\le g\le n-3$, obtained by identifying the center of $K_{1,g}$ with an end of the path $P_{n-g}$, the characteristic set is an edge.

Result: The conjecture is true.

Let $m=n-g$. Write the spine as $v_1\cdots v_m$, with $g\ge2$ leaves attached at $v_m$.

Use the Perron-component criterion: a vertex $x$ of a tree is characteristic iff at least two components of $T-x$ have maximal Perron value, where the Perron value of a component is the spectral radius of the inverse principal Laplacian of that component.

Pendant vertices cannot be characteristic. Also $v_m$ is not characteristic: after deleting $v_m$, the leaf-components have Perron value $1$, while the path component on $m-1\ge2$ vertices has Perron value $>1$.

Suppose, for contradiction, that some internal spine vertex $v_i$, $2\le i\le m-1$, is characteristic. Put

$$q=i-1,\qquad \ell=m-i.$$

Then the left path component and the right path-star component must have equal Perron value, equivalently equal least principal-Laplacian eigenvalue.

The left path component has least eigenvalue

$$\lambda=2-2\cos\theta,\qquad \theta=\frac{\pi}{2q+1}.$$

If $q=1$, then $\lambda=1$, while the right component has least eigenvalue $<1$ by the Rayleigh quotient using the all-one vector, contradiction. Hence $q\ge2$.

Let $y_j$ be the positive least-eigenvector values on the right spine, $j=1,\dots,\ell$, starting next to $v_i$. The recurrence gives

$$y_j=A\sin(j\theta).$$

Positivity gives $\ell<2q+1$. If $t$ is the common leaf value, the leaf equation gives $t=y_\ell/(1-\lambda)$, and the center equation gives

$$\frac{\sin((\ell-1)\theta)}{\sin(\ell\theta)} =(1-\lambda)-\frac{g\lambda}{1-\lambda}.$$

Thus

$$g=G_\ell(\theta):= \frac{(2\cos\theta-1)\bigl(\sin((\ell+1)\theta)-\sin(\ell\theta)\bigr)} {(2-2\cos\theta)\sin(\ell\theta)}. \tag{1}$$

Now set $N=2q+1$. For $1\le \ell<N$,

$$G_\ell(\theta)= \frac{(2\cos\theta-1)\cos((2\ell+1)\theta/2)} {2\sin(\theta/2)\sin(\ell\theta)}.$$

So $G_{q-1}(\theta)=1$, $G_q(\theta)=0$, and $G_\ell(\theta)\le0$ for $\ell\ge q$. Since $g\ge2$, (1) forces $\ell\le q-2$.

Let $\zeta=e^{i\theta}$. The map $\zeta\mapsto \zeta^{N-2}$ is a Galois automorphism because $\gcd(N-2,2N)=1$. If $G_\ell(\theta)=g\in\mathbb Z$, then also

$$G_\ell((N-2)\theta)=g.$$

But for $1\le\ell\le q-2$, a direct trigonometric comparison gives

$$G_\ell(\theta)>G_\ell((N-2)\theta).$$

Indeed, writing $t=\theta/2$, this inequality reduces to

$$\frac{\cos 2t}{(2\cos2t+1)\sin t}>\frac{\cos4t}{\sin5t},$$

and after cross-multiplication the difference is

$$\cos2t\sin5t-(2\cos2t+1)\sin t\cos4t =\frac{\sin3t+\sin t}{2}>0.$$

Contradiction.

Therefore no vertex of $P_{n-g,g}$ is characteristic. Since the characteristic set of a tree is always either one vertex or one edge, it must be an edge.

Audit: the proof uses exactly the paper’s path-star range $2\le g\le n-3$. If one allowed $g=1$, the statement would fail for odd paths, so this hypothesis is essential.

Citation: The conjecture is from Pandey--Patra, “Different central parts of trees and their pairwise distances,” arXiv:2004.02197. The Perron-component characterization is due to Kirkland--Neumann--Shader, Linear and Multilinear Algebra 40 (1996), building on Fiedler/Merris. The resolution above is self-contained beyond those standard facts.