On a conjecture of Eǧecioǧlu and Iršič

Abstract

In 2021, {Ö}. Eǧecioǧlu, V. Iršič 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\ge 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.