Given a vertex $x$ of a graph, call the subgraph induced by all vertices of distance $\le n$ from $x$ the $n$-neighbourhood of $x$, denoted $N_n(x)$.

Let $G$ be a regular graph of diameter $n+1$. For $G$ to come "close" to meeting the Moore bound, it must have a sort of "local $n$-arc-transitivity": for any vertex $x$, $N_n(x)$ must

  • be isomorphic to $N_n(y)$ for every vertex y,
  • cover at least half of $G$, and
  • have an automorphism (of $N_n(x)$, not necessarily of $G$) taking any $n$-arc starting at $x$ to any other.

Moore graphs themselves are known to be very rare, and generalized Moore graphs (the "next-best thing") are conjectured to be bounded in diameter, at least for any fixed degree.[1] Meanwhile, it is known that a finite graph can only be $s$-arc transitive for $s \le 7$ when the degree is $> 2$.

In particular, cubic graphs can only be $s$-arc transitive for $s \le 5$, and the largest known cubic generalized Moore graph is Tutte's 12-cage, with diameter $6$.[1] After that, cubic graphs seem to rapidly fall away from the Moore bound (so far as I am aware).

Could there be any connection here?

[1] Leif Jørgensen, Variations and Generalizations of Moore Graphs. http://people.math.aau.dk/~leif/foredrag/Bandung-MooreGraphs.pdf

(Not sure if this question is too vague and should be made community-wiki: I'm leaving it as-is, but won't be offended if someone changes it.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.