Update: I found $m_2\le 32$, which means that my upper bound ${\ref{bound}}$ is not optimal.
Frog puzzle is played on a connected graph as follows:
Place one frog on each vertex of the graph to start the puzzle.
The goal of the puzzle is to move all frogs to a given vertex.
All $f$ frogs on vertex $v$ can be moved to vertex $w$ if and only if:
- Both vertices $v,w$ contain at least one frog.
- There exists a path from $v$ to $w$ consisting of $f$ unique edges.
For example, frog puzzle is solvable on any vertex of a path graph.
I'm interested in solving the puzzle on star subgraphs of "dandelion graphs". They can be described as:
Definition. Let $D_{m,n}$ represent a "dandelion graph" consisting of a vertex $v_0$ of degree $m+1$, where:
- $v_0$ is connected to $m$ leaf vertices $\{s_1,\dots,s_m\}=V(S_m)$, i.e. $v_0$ is a center of a star $S_m$.
- $v_0$ is connected to a path $P_n$ whose vertices are $V(P_n)=\{p_1,\dots,p_n\}$.
That is, star $S_m$ and path $P_n$ are subgraphs of $D_{m,n}$ that share only a single vertex $v_0$.
Then, $|V(D_{m,n})|=m+n+1$. For example, frog puzzle is solvable on vertex $p_3$ of a $D_{6,15}$ dandelion.
Question. Given $k\in\mathbb N$, what is the smallest $m\gt k$ such that $D_{m,m-k}$ is "solvable in a vertex" $s\in V(S_m)$ ?
We say that given graph "is solvable in a vertex" if the frog puzzle is solvable in that vertex.
Motivation: I have proven that $s\in V(S_m)$ is solvable if $n\ge m$. It remains to consider cases like the given question. (I also know that every vertex of a dandelion is solvable if $n\ge 2m+3$, but asking about all vertices for all $n\lt 2m+3$ is maybe too much.)
Let $m_k$ be the smallest $m$ that answers the question for the given $k$.
I believe that $m_1=14$. This is because $D_{14,13}$ is indeed solvable in some $s\in V(S_m)$,
and because for smaller $m$, the $D_{m,m-1}$ is not solvable in $s$ (assuming my computer search is ok).
For $k>1$, I can only find upper bounds. That is, I have the following: $$m_{k+1}\le 3m_k -2k + 5\label{bound}\tag*{(*)}$$
This is not hard to see. I inductively took the solution of $D_{m_k,m_k-k}$, then connected one extra leaf vertex $s'$ to $v_0$ and then kept connecting an additional vertex both to $v_0$ and to the end of the path subgraph until I could move frogs to that one extra leaf vertex $s'$ and then eventually move all remaining frogs to $s$ in which the graph needs to be solvable. It turns out that extending the graph to $D_{m_{k+1},m_{k+1}-(k+1)}=D_{m',n'},n'=3(m_k-k)+4$ works, which gives the upper bound.
Could this upper bound be the answer (equality holds?), or is there a better upper bound?
Update: My upper bound gives $m_2\le 45$, but I found $m_2\le 32$. Can we do even better?