Return to Answer

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&473\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&473\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

Update: By request from martin, here is the sage code for it. For N=3, n=473 it takes .2 seconds to find the hamiltonian cycle, for N=4, n=9641 it takes 290 seconds on my computer.

def getgraph(n,N,path):
    powers=[(i+1)^N for i in range(ceil((2*n)^(1/N)))]
    G=Graph()
    G.add_vertices([1,..,n])
    edges=[]
    for p in powers:
        for i in range(1,ceil(p/2)+1):
            if i<=n and p-i<=n and p-i>0:
                edges.append([i,p-i])

    if path:   #add an extra vertex connected to all others
        G.add_vertex(0)  #to get path from cycle
        for i in [1,..,n]:
            edges.append([0,i])
    G.add_edges(edges)
    return G

path=False
n=473
N=3
time G=getgraph(n,N,path)
time hami=G.hamiltonian_cycle()

l=hami.cycle_basis()[0]
print [l[(i+l.index(int(not(path))))%len(l)] for i in range(len(l))]

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&437\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&473\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&437\\4&?(\geq9254)&9641 \\5&?&?(>490000)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9235$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.

This is a to long for a comment:

Let $G(n,N)$ Micah's graph with vertices the numbers $1,..,n$ and edges $\{i,j\}$ if $i+j$ is a power of $N$. Your condition is satisfied if and only if $G$ contains a Hamiltonian path. (And the analogues question for a cycle if and only if $G$ contains a Hamiltonian cycle).

Let $m(N)$ be the smallest $n$ such that $G(n,N)$ contains a Hamiltonian path and $m_c(N)$ the smallest $n$ such that $G(n,N)$ contains a Hamiltonian cycle.

From a some calculations with sage one can see that $$\begin{array}{c|cc}N&m(N)&m_c(N)\\\hline1&2&3\\2&15&32\\3&305&437\\4&?(\geq9254)&9641 \\5&?&?(\geq490463)\end{array} $$ Example for $15$, $32$ and $305$ are already in your question, I calculated examples of the 473 and the 9641.

For the entries with questions marks: these are just some guesses. For $m(4)$, one can quickly see, with the help of sage that $G(9253,4)$ does not have a Hamiltonian path, and neither $G(n,4)$ for $n=9252, 9251, 9250,\dots$ or $9210$. But so far I could not find a Hamiltonian path in $G(9253,4)$, maybe somebody else can give it a try. Similarly, $G(490462,5)$ does not contain a Hamiltonian cycle.

I find the argument in your "Additional Information" quite convincing and would expect that most graphs with more than $m(N)$ (or $m_c(N)$) satisfy your condition; with possibly a few exceptions just above $m(N)$ (or $m_c(N)$). Maybe a probabilistic argument could turn this into a proof.

One could also ask about the asymptotics of $m(N)$ and $m_c(N)$ or find lower bounds for them.