For any two graphs G and H of order n, with adjacency matrices A_G and A_H, let mathbf e be the all-one vector and define W_G=[mathbf e,A_G mathbf e,…,A_G^n-1mathbf e] and W_H=[mathbf e,A_H mathbf e,…,A_H^n-1mathbf e]. The Liu–Siemons conjecture asserts that W_G=W_H implies that G and H are isomorphic.

Liu–Siemons conjecture on walk-matrix equivalence

For any two graphs $G$ and $H$ of order $n$ , with adjacency matrices $A_G$ and $A_H$ , let $\mathbf e$ be the all-one vector and define $W_G=[\mathbf e,A_G\mathbf e,\ldots,A_G^{n-1}\mathbf e]$ and $W_H=[\mathbf e,A_H\mathbf e,\ldots,A_H^{n-1}\mathbf e]$ . The Liu–Siemons conjecture asserts that $W_G=W_H$ implies that $G$ and $H$ are isomorphic.

References

Primary source

arXiv

Additional references

A Characterization of Walk-Matrix Equivalence at Corank Two via Reciprocal WQH Switching — arXiv — Chaochao Zhu, Qin Yue

algebraic-graph-theory spectral-graph-theory

Posted 1 week ago · edited 1 week ago

Progress summary

Refreshed 1 week ago

Claimed solved

A new unrefereed preprint claims the conjecture is false and gives counterexamples in every sufficiently large size, but the claim has not been independently checked.

The Liu–Siemons conjecture concerns when graphs with equivalent walk matrices must be structurally equivalent. Chaochao Zhu and Qin Yue claim a complete disproof and replacement by a switching classification.

Known results

If a graph’s walk matrix has rank at least $n-1$ , its adjacency matrix is determined by that walk matrix; in this range, equality corresponds to graph isomorphism.

Recent preprint

Chaochao Zhu and Qin Yue claim a complete characterization at corank two via reciprocal WQH switching, no examples through order $9$ , and connected counterexamples for every $n \ge 10$ . The source is an unrefereed preprint, so this disproof and classification remain unverified.

Current status (as of September 2026): The conjecture is claimed false, with a claimed structural classification and connected examples for every $n \ge 10$ , but the preprint’s results remain unverified.

Sources

No solutions have been posted yet.