In 2021, { \"O}. E\v{ g}ecio\v{ g}lu, V. Ir\v{ s}i\v{ c} introduced the concept of Fibonacci-run graph $\mathcal{ R}_{ n}$ as an induced subgraph of Hypercube. They conjectured that the diameter of $\mathcal{ R}_{ n}$ is given by $n-\lfloor(1+\frac{ n}{ 2})^{ \frac{ 1}{ 2}}-\frac{ 3}{ 4}\rfloor$. In this paper, we introduce the novel concept of distance-barriers between vertices in $\mathcal{ R}_{ n}$ and provide an elegant method to give lower bound for the diameter of $\mathcal{ R}_{ n}$ via distance-barriers. By constructing different types of distance-barriers, we show that the conjecture does not hold for all $n\geq 230$ and some of $n$ between $91$ and $229$. Furthermore, lower bounds for the diameter of some Fibonacci-run graphs are obtained, which turn out to be better than the result given in the conjecture.
Categories: math.CO