Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.14610 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911764926431232 |
|---|---|
| author | Wei, Jianxin Yang, Yujun |
| author_facet | Wei, Jianxin Yang, Yujun |
| contents | 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\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14610 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a conjecture of Eǧecioǧlu and Iršič Wei, Jianxin Yang, Yujun Combinatorics 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\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. |
| title | On a conjecture of Eǧecioǧlu and Iršič |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.14610 |