Let $G$ be a graph on $n$ vertices, $D$ a subset of vertices. We interpret $D$ as a pebble configuration on $G$. A vertex $v$ of $G$ is occupied if it is in $D$, unoccupied otherwise. A move takes a pebble from an occupied vertex and moves it to an adjacent unoccupied vertex.
The mobility of $D$, denoted by $m(D)$ is the number of possible moves. The $k$-mobility of $G$, denoted by $m_k(G)$ is the maximum mobility of any vertex subset of size $k$. The mobility of $G$, denoted by $m(G)$, is the maximum mobility of any vertex subset. (Btw, have these concepts official names? Are they studied?)
It is easy to show that $m_k(G)$ is symmetric on the segment $[0,n]$. It is also easy to show that $m(G)$ equals the number of edges in a largest bipartite spanning subgraph.
I am interested in an aspect of the behavior of $m_k(G)$ (for fixed $G$). Let $m=\lfloor\frac n2\rfloor$. The question is: is $m_k(G)$ weakly unimodal on the segment $[0,m]$, in other words, is there an index $t$ such that $m_{i-1}(G)\leq m_i(G)$ for $i\leq t$ and $m_{i+1}(G)\geq m_i(G)$ for $i\geq t$. A proof (or counterexample) for trees would already help a lot.
Some partial results (for trees, and on the segment $[0,m]$):
- It is easy to find an example where the function becomes stationary, then increases further.
- Computer runs on small random trees have not produced a counterexample.
- If the function decreases, it decreases by exactly $1$ (my proof of this is not entirely trivial).
- A local maximum can be anywhere, for star graphs it is at $i=1$, for cycles it is a $i=m$.