Snakequake!
Feb. 24th, 2026 08:04 pmSomeone else has written about Snake!
You might remember my webpage on the problem, which unfortunately they don't seem to have turned up in their lit review (I guess that's what happens when you don't publish properly :P ).
But these people are studying the same problem and have turned up some cool new results!
One thing to beware of, they numbered their theta graphs differently than I did. Their Θ(2,2,k) is my Θ1,1,k-1.
But: They showed that if G is bipartite with an odd number of vertices, then the only way it can be winnable is to include some Θ1,1,k as a spanning subgraph. As a consequence, they derive that determining winnability is NP-hard!
Moreover, they showed that if a winnable graph does not have a Hamilton cycle, it must have girth at most 6, something I certainly never thought of! They also have an example to show that this is tight, but the example seems incorrect, in that it seems to have a Hamilton cycle? Regardless though the bound is tight, as is shown by Θ2,2,2.
Note that while I didn't put it on the webpage, I also had an inequality about cycles, only mine was about the largest cycle. I've probably written about it here before, but: Let c(G) be the length of the largest cycle, and let k(G) be the size of the largest clique that can be found at the end of a Hamilton path. Then for a winnable graph G with n vertices, k(G)+c(G)≥n, meaning in particular that c(G)≥n/2. But I never looked at the smallest cycle!
Anyway yeah cool results! Obviously I've written to them. :)
-Harry
You might remember my webpage on the problem, which unfortunately they don't seem to have turned up in their lit review (I guess that's what happens when you don't publish properly :P ).
But these people are studying the same problem and have turned up some cool new results!
One thing to beware of, they numbered their theta graphs differently than I did. Their Θ(2,2,k) is my Θ1,1,k-1.
But: They showed that if G is bipartite with an odd number of vertices, then the only way it can be winnable is to include some Θ1,1,k as a spanning subgraph. As a consequence, they derive that determining winnability is NP-hard!
Moreover, they showed that if a winnable graph does not have a Hamilton cycle, it must have girth at most 6, something I certainly never thought of! They also have an example to show that this is tight, but the example seems incorrect, in that it seems to have a Hamilton cycle? Regardless though the bound is tight, as is shown by Θ2,2,2.
Note that while I didn't put it on the webpage, I also had an inequality about cycles, only mine was about the largest cycle. I've probably written about it here before, but: Let c(G) be the length of the largest cycle, and let k(G) be the size of the largest clique that can be found at the end of a Hamilton path. Then for a winnable graph G with n vertices, k(G)+c(G)≥n, meaning in particular that c(G)≥n/2. But I never looked at the smallest cycle!
Anyway yeah cool results! Obviously I've written to them. :)
-Harry
