On the nonexistence of almost Moore digraphs with self-repeats
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913564880535552 |
|---|---|
| author | Messegué, Arnau Miret, Josep Maria |
| author_facet | Messegué, Arnau Miret, Josep Maria |
| contents | An almost Moore digraph is a diregular digraph of degree $d>1$, diameter $k>1$ and order $d+d^2+ \cdots +d^k$.
Their existence has only been shown for $k=2$. It has also been conjectured that there are no more almost Moore digraphs, but so far their nonexistence has only been proven for $k=3,4$ and for $d=2,3$ when $k\geq 3$.
In this paper we study the structure of the subdigraphs of an almost Moore digraph induced by the vertices fixed by an automorphism determined by a power of the permutation $r$ of repeats of the digraph. We deduce that each almost Moore digraph of degree $d$ and diameter $k$ with self-repeats has such a subdigraph whose vertices have order $\leq d-1$ under $r$. From this, we extend the results about the nonexistence of almost Moore digraphs with self-repeats of degrees 4 and 5 to those whose diameter is large enough with respect to the degree. More precisely, we prove their nonexistence when $k\geq 2(d-1)$ if $k$ is odd and when $k \geq 2(d-1)^2$ if $k$ is even. We also show that these findings jointly with other results imply that there are no almost Moore digraphs with self-repeats for degrees $d$, $6\leq d\leq 12$, and $k>2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20226 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the nonexistence of almost Moore digraphs with self-repeats Messegué, Arnau Miret, Josep Maria Combinatorics An almost Moore digraph is a diregular digraph of degree $d>1$, diameter $k>1$ and order $d+d^2+ \cdots +d^k$. Their existence has only been shown for $k=2$. It has also been conjectured that there are no more almost Moore digraphs, but so far their nonexistence has only been proven for $k=3,4$ and for $d=2,3$ when $k\geq 3$. In this paper we study the structure of the subdigraphs of an almost Moore digraph induced by the vertices fixed by an automorphism determined by a power of the permutation $r$ of repeats of the digraph. We deduce that each almost Moore digraph of degree $d$ and diameter $k$ with self-repeats has such a subdigraph whose vertices have order $\leq d-1$ under $r$. From this, we extend the results about the nonexistence of almost Moore digraphs with self-repeats of degrees 4 and 5 to those whose diameter is large enough with respect to the degree. More precisely, we prove their nonexistence when $k\geq 2(d-1)$ if $k$ is odd and when $k \geq 2(d-1)^2$ if $k$ is even. We also show that these findings jointly with other results imply that there are no almost Moore digraphs with self-repeats for degrees $d$, $6\leq d\leq 12$, and $k>2$. |
| title | On the nonexistence of almost Moore digraphs with self-repeats |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.20226 |