1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Additionally $trace{A}=\sum\lambda_i = \lfloor{\sqrt{\frac{N}{2}}}\rfloor$. $\endgroup$ – pisoir Oct 7 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.