2
$\begingroup$

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.)

$\endgroup$

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.