The critical group of a clique-inserted graph

NEW

Problem: Reconstructed conjecture: for every connected finite simple non-bipartite $d$-regular graph $G$, with clique-inserted graph $C(G)$, critical group $K(\cdot)$, and $\beta(G)=|E(G)|-|V(G)|+1$, the Chen–Zhang map $f^*:K(C(G))\to K(G)$ satisfies

$$\ker(f^*)\cong \mathbb Z_{d+2}^{\,2}\oplus \mathbb Z_{d(d+2)}^{\,\beta(G)-2}.$$

This is the natural reading because the right-hand side is a candidate kernel inside $K(C(G))$.

Result: The conjecture is false. Let $G=K_5$. Then $G$ is connected, non-bipartite, $4$-regular, and

$$\beta(G)=10-5+1=6.$$

The conjectured kernel is

$$H=\mathbb Z_6^2\oplus \mathbb Z_{24}^4,$$

so

$$\dim_{\mathbb F_2} H/2H=6.$$

But $K(K_5)$ has order $\tau(K_5)=5^3$, hence odd. Therefore every homomorphism

$$K(C(K_5))\to K(K_5)$$

kills the entire Sylow $2$-subgroup of $K(C(K_5))$, so the $2$-rank of its kernel equals the $2$-rank of $K(C(K_5))$.

Now compute that rank. The vertices of $C(K_5)$ are ordered pairs $(i,j)$, $i\ne j$, with adjacency

$$(i,j)\sim(j,i),\qquad (i,j)\sim(i,k)\quad(k\ne i,j).$$

There are $20$ vertices and the graph is $4$-regular, so over $\mathbb F_2$ its Laplacian equals its adjacency matrix $A$.

For $x=(x_{ij})\in\ker A$, set $s_i=\sum_{k\ne i}x_{ik}$. The equation $(Ax)_{ij}=0$ gives

$$x_{ij}+x_{ji}=s_i.$$

Swapping $i,j$ gives $s_i=s_j$, so all $s_i=s$. Summing over all $i$,

$$s=\sum_i s_i=\sum_{i<j}(x_{ij}+x_{ji})=10s=0,$$

hence $s=0$. Thus $x_{ij}=x_{ji}$, and the remaining condition is that the corresponding edge-labeling of $K_5$ has even degree at every vertex. This is the binary cycle space of $K_5$, of dimension

$$|E(K_5)|-|V(K_5)|+1=6.$$

So $\operatorname{rank}_{\mathbb F_2}A=20-6=14$.

For a connected graph $X$,

$$\dim_{\mathbb F_2}K(X)/2K(X)=|V(X)|-1-\operatorname{rank}_{\mathbb F_2}L_X.$$

Therefore

$$\dim_{\mathbb F_2}K(C(K_5))/2K(C(K_5))=20-1-14=5.$$

Hence any kernel $K(C(K_5))\to K(K_5)$ has $2$-rank $5$, while the conjectured group has $2$-rank $6$. Thus

$$\ker(f^*)\not\cong \mathbb Z_6^2\oplus \mathbb Z_{24}^4.$$

Audit: $K_5$ satisfies all reconstructed hypotheses, and the contradiction is with the exact claimed isomorphism.

Citation: Context: Haiyan Chen and Fuji Zhang, “The critical group of a clique-inserted graph,” Discrete Mathematics 319 (2014), 24–32. The counterexample above is self-contained.