Perturbation of Fiedler vector: interest for graph measures and shape analysis

NEW

Problem: Reconstructed statement: let $G$ be a finite connected simple undirected graph on vertices $0,\dots,n-1$, with combinatorial Laplacian $L$. Let $v$ be a vertex where a Fiedler vector of $G$ attains a global maximum or minimum. For $x>0$, form $\widetilde G_x$ by adding a new vertex $n$ and one edge $(v,n)$ of weight $x$. The conjecture claims that every Fiedler vector of $\widetilde G_x$ has the new vertex $n$ as a global maximum or minimum.

This is the natural formalization of Conjecture 1 in Lefevre--Fraize--Germanaud, where Proposition 1 defines exactly this weighted pendant-vertex perturbation.

Result: The conjecture is false.

Take $G$ on vertices $0,\dots,9$ with edge set

$$\begin{aligned} E=\{&(0,1),(0,4),(0,5),(1,3),(1,4),(1,6),(1,9),\\ &(2,4),(2,5),(2,8),(3,4),(3,8),(6,7),(7,8)\}. \end{aligned}$$

Its Laplacian characteristic polynomial factors as

$$t(t-3)(t-2)(t^2-7t+5) (t^5-16t^4+95t^3-257t^2+308t-127).$$

Sturm checking shows the quintic has no root below

$$\lambda_2=\frac{7-\sqrt{29}}2\approx0.8074175964,$$

so this is the algebraic connectivity. A corresponding Fiedler vector is proportional to

$$(-1,\,4,\,-(5+\sqrt{29})/2,\,-1,\,-1,\,-(5+\sqrt{29})/2,\,-1,\,-(5+\sqrt{29})/2,\,-(5+\sqrt{29})/2,\,2(5+\sqrt{29})).$$

Thus vertex $v=2$ is a global minimum of a Fiedler vector of $G$.

Now add a new vertex $10$ joined to $2$ with weight $x=100$. The nonzero characteristic factor of the new Laplacian is

$$\begin{aligned} P(t)=&t^{10}-228t^9+5633t^8-61600t^7+377164t^6-1410090t^5\\ &+3318861t^4-4894988t^3+4343849t^2-2096610t+419100. \end{aligned}$$

Sturm signs give exactly one root in $(0.738,0.739)$ and none in $(0,0.738)$, so the Fiedler eigenvalue is the root $\mu\in(0.738,0.739)$.

Normalize its Fiedler vector $u$ by $u_{10}=1$. Exact row reduction of $(\widetilde L-\mu I)u=0$ gives

$$u_5-1 = -\frac{\mu(\mu-2)(\mu^2-7\mu+5)Q(\mu)}{D(\mu)},$$

where

$$Q(t)=t^6-119t^5+1643t^4-8942t^3+22579t^2-25351t+9481,$$

and

$$D(t)=t^{10}-128t^9+2833t^8-28300t^7+157164t^6-523690t^5 +1069861t^4-1318888t^3+925049t^2-321710t+38100.$$

On $t\in(0.738,0.739)$, interval arithmetic gives

$$t>0,\quad t-2<0,\quad t^2-7t+5>0,\quad Q(t)<0,\quad D(t)<0.$$

Hence $u_5-1>0$, so $u_5>u_{10}$. Also exact row reduction gives

$$u_9=\frac{100(\mu-3)(\mu^5-16\mu^4+95\mu^3-257\mu^2+308\mu-127)}{D(\mu)}<0,$$

so $u_{10}=1$ is neither a maximum nor a minimum. Multiplying the eigenvector by $-1$ does not change this conclusion.

Thus the new vertex $10$ is not an extremum of the Fiedler vector, contradicting the conjecture.

The failure comes from a non-strict extremum in the original graph: vertex $2$ is tied with $5,7,8$. A natural repair would require $v$ to be a strict extremum, but that repaired statement is not needed for the counterexample above.

Citation: No prior disproof is used here. The conjecture is from Lefevre, Fraize, and Germanaud, “Perturbation of Fiedler vector: interest for graph measures and shape analysis,” arXiv:2306.04327.