I am having undirected graphs with adjacency matrices which have a regular Hankel-like form, e.g., $ $ A=\begin{pmatrix}0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & (6\times 0 \text{ then } 1) \ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & (5 \times 0 \text{ then } 1)\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \dots\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & \dots\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \dots\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & \dots\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \dots\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \dots\ \vdots \end{pmatrix}$ $

In other words, a sequence “0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, $ \dots$ “, where $ 1$ s are at positions 3, 8, 15, 24, 35, etc. ($ n^2-1, n\in \mathbb{N}$ ).

Since I could not find anything about these types of graphs, I would like to know if they have a name (afaik there exist Toeplitz graphs), or if there is something known about their properties. The motivation for this problem comes from the question posted here: MO

Some minor (“brute-force”) observations and known information:

1. For the size $ N<14$ the graph is disconnected.
2. At least for the size $ N<25$ the graph is planar.
3. For $ N=15, 16, 17, 23$ and probably for all $ N>24$ , the graph contains a Hamiltonian path (conjecture).
4. First Hamiltonian cycle is probably for $ N=32$ .

Obviously the graph is quite sparse, so Dirac’s, Ore’s, Chvatal’s theorem for Hamiltonicity cannot be applied here (I have a feeling that it remains very sparse also as $ N\to\infty$ , since $ n$ grows faster than $ N$ and thus also the zeros fill up the adjacency matrix more and more).

Since the matrix is quite regular, I was wondering if some approach using the relation between the determinant of the matrix and spanning subgraphs (e.g. Determinants in Graph Theory) cannot be applied here. But I was unable to come up with something reasonable so far. Any ideas?

Thanks.