The complete-graph product recurrence order conjecture

About 18 years old · traced to 2008

Let $K_k$ be the complete graph on $k$ vertices, let $P_n$ be the path graph on $n$ vertices, and consider the spanning-tree recurrence for the graph product $K_k\times P_n$ . Complete-graph product recurrence order conjecture. The recurrence for the graph $K_k\times P_n$ has order $k$ . This predicts an exact recurrence order for spanning-tree counts of complete-graph products with paths; the source provides no evidence of resolution.

References

Primary source

Paul Raff, “Spanning Trees in Grid Graphs”, arXiv:0809.2551 (2008).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Open

The conjecture remains open: no public proof, counterexample, or other progress was found.

A 2008 paper conjectures that the spanning-tree recurrence for $K_k \times P_n$ has exact order $k$ . It presents this as an experimentally motivated conjecture, not a theorem.

Known results

For a graph $G$ with $k$ vertices, the spanning-tree sequence for $G \times P_n$ satisfies a linear recurrence of order at most the Bell number $B_k$ .

Current status (as of September 2026): The conjectured exact order $k$ remains unproved and unrefuted; only the general upper bound of $B_k$ is recorded.

Sources

No solutions have been posted yet.