3
$\begingroup$

Call a (finite and connected) graph $k$-distance-transitive if its symmetry group acts transitively on the pairs in each one of the sets

$$D_\delta:=\{(i,j)\in V\times V\mid \mathrm d(i,j)=\delta\},\qquad\text{for all $\delta\in\{0,...,k\}$}.$$

For $k=\mathrm{diam}(G)$ (the diameter of $G$), these are the distance-transitive graphs.

Question: Is it known that if $k$ is just large enough (e.g. relative to $\mathrm{diam}(G)$, or in an absolute sense), that every $k$-distance-transitive graph is already distance-transitive?

Or are there examples of $k$-distance-transitive graphs of arbitrary large diameter, that are not distance-transitive even if $k=\mathrm{diam}(G)-1$?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ It seems you're considering connected graphs. You're also assuming graphs are finite, right? $\endgroup$
    – YCor
    Commented Jun 13, 2020 at 12:08
  • $\begingroup$ @YCor Yes, I will edit this in. What has this question to do with (metric) geometry? $\endgroup$
    – M. Winter
    Commented Jun 13, 2020 at 12:09
  • 1
    $\begingroup$ Metric geometry is, to a large extent, the study of metric spaces, including their isometry groups. Connected graphs provide a very nice and important supply of metric spaces. The notion of distance transitivity (isometry group is transitive on pairs at given distance) is a purely metric notion. $\endgroup$
    – YCor
    Commented Jun 13, 2020 at 12:09
  • $\begingroup$ Just a small comment: if we have a $k$-distance-transitive graph, and the girth is also large (I think at least $2k$), then it must also be $k$-arc-transitive. It is known that there are no finite $8$-arc-transitive graphs except cycles. So, if you want examples with large $k$, then you need small(ish) girth. $\endgroup$
    – verret
    Commented Aug 3, 2020 at 4:54
  • 3
    $\begingroup$ Actually, here's an improvement on this argument: it is known that there is an absolute constant $c$ such that, in a finite $2$-arc-transitive graph, fixing (pointwise) a ball of radius $c$ around a vertex fixes everything. (This is due to Trofimov and Weiss. I think you can take $c$ to be $5$ or $6$.) Now, if your family is going to be $k$-distance-transitive for large $k$ smaller than the diameter, with $k$ growing, then I think it cannot have the property above. In particular, the large $k$ examples cannot be $2$-arc-transitive. In particular, they must have girth $3$. $\endgroup$
    – verret
    Commented Aug 3, 2020 at 4:59

1 Answer 1

Reset to default
1
$\begingroup$

Not an answer, but a related result that I wanted to share. Note that $k$-distance-transitivity is generalized by $k$-walk-regularity. In

the authors prove the following (see Corollary 6.4):

Theorem. Let $G$ be a $k$-walk-regular graph of degree $d$ with an eigenvalue $\theta\not\in\{-d,d\}$ of multiplicity at most $k$. If $k\ge 2$, then $G$ is distance-regular.

So $k$-walk-regular graphs that are not distance-regular must have only eigenvalues of large multiplicity (excluding $\theta=\pm d$). Maybe something similar is true in the case of distance-transitivity.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .