The path-matrix conjecture for 2-connected graphs

An infinite family of 2-connected counterexamples

The conjecture is false even for planar chordal graphs. For each integer $m\geq1$, let

$$G_m=K_2\vee\overline{K_m}.$$

More explicitly, its vertices are

$$V(G_m)=\{u,v,x_1,\ldots,x_m\},$$

and its edges are

$$E(G_m)=\{uv\}\cup\{ux_i,vx_i:1\leq i\leq m\}.$$

Thus $G_m$ consists of $m$ triangles sharing the edge $uv$. Removing any $x_i$ leaves a connected graph, while removing either $u$ or $v$ leaves a star. Consequently $G_m$ is 2-connected.

Write $p(a,b)$ for the maximum number of internally vertex-disjoint paths between distinct vertices $a,b$. If one endpoint is $x_i$, its degree is two, so there are at most two such paths. There are also two explicitly:

$$x_iux_j,\qquad x_ivx_j \qquad (i\neq j),$$

and

$$x_iu,\qquad x_iv u.$$

The analogous paths connect $x_i$ to $v$. Hence

$$p(x_i,x_j)=2\quad(i\neq j), \qquad p(x_i,u)=p(x_i,v)=2.$$

For the two vertices on the common edge, the paths

$$uv,\qquad ux_1v,\qquad ux_2v,\qquad\ldots,\qquad ux_mv$$

are internally vertex-disjoint. Since both $u$ and $v$ have degree $m+1$, this is optimal, and therefore

$$p(u,v)=m+1.$$

In the vertex order $x_1,\ldots,x_m,u,v$, the path matrix is

$$P(G_m)= \begin{pmatrix} 2(J_m-I_m)&2\mathbf 1_{m\times2}\\ 2\mathbf 1_{2\times m}&(m+1)(J_2-I_2) \end{pmatrix}.$$

Every vector supported on the first $m$ coordinates whose coordinates sum to zero is an eigenvector with eigenvalue $-2$. This gives multiplicity $m-1$. Likewise, the vector supported on $u,v$ with coordinates $1,-1$ is an eigenvector with eigenvalue $-(m+1)$.

The remaining two-dimensional invariant subspace consists of vectors constant on $\{x_1,\ldots,x_m\}$ and constant on $\{u,v\}$. The corresponding quotient matrix is

$$Q_m= \begin{pmatrix} 2(m-1)&4\\ 2m&m+1 \end{pmatrix}.$$

Its trace and determinant are

$$\operatorname{tr}(Q_m)=3m-1, \qquad \det(Q_m)=2(m^2-4m-1).$$

Consequently, the complete characteristic polynomial is

$$\det(\lambda I-P(G_m)) =(\lambda+2)^{m-1}(\lambda+m+1) \bigl(\lambda^2-(3m-1)\lambda+2(m^2-4m-1)\bigr),$$

and the two remaining eigenvalues are

$$\lambda_{\pm}(m) =\frac{3m-1\pm\sqrt{m^2+26m+9}}{2}.$$

For every integer $m\geq5$, their sum and product are positive:

$$\lambda_+(m)+\lambda_-(m)=3m-1>0, \qquad \lambda_+(m)\lambda_-(m)=2(m^2-4m-1)>0.$$

Therefore both are strictly positive. All other path eigenvalues are strictly negative, so

$$\#\{\lambda\in\operatorname{Spec}(P(G_m)):\lambda>0\}=2 \qquad(m\geq5).$$

An explicit seven-vertex counterexample

Taking $m=5$ gives the 2-connected graph with edges

$$uv,\quad ux_1,vx_1,\quad ux_2,vx_2,\quad ux_3,vx_3, \quad ux_4,vx_4,\quad ux_5,vx_5.$$

Its path matrix is

$$P(G_5)= \begin{pmatrix} 0&2&2&2&2&2&2\\ 2&0&2&2&2&2&2\\ 2&2&0&2&2&2&2\\ 2&2&2&0&2&2&2\\ 2&2&2&2&0&2&2\\ 2&2&2&2&2&0&6\\ 2&2&2&2&2&6&0 \end{pmatrix}.$$

The characteristic polynomial factors as

$$\det(\lambda I-P(G_5)) =(\lambda+2)^4(\lambda+6)(\lambda^2-14\lambda+8),$$

and thus its path spectrum is

$$\operatorname{Spec}(P(G_5)) =\{-2,-2,-2,-2,-6,7-\sqrt{41},7+\sqrt{41}\}.$$

Since $\sqrt{41}<7$, both $7-\sqrt{41}$ and $7+\sqrt{41}$ are positive. This directly contradicts the claim that every 2-connected graph has exactly one positive path eigenvalue.

The assertion refuted here is Conjecture 1 of A. P. Narke, P. P. Malavadkar, and M. M. Shikare, Bounds on Path Energy of Graphs, current arXiv version 4 (2024), https://arxiv.org/abs/2205.05100. The path matrix used above is exactly the internally vertex-disjoint-path matrix in Definition 1.1 of that source.