On $\ell$-distance-balancedness of cubic Cayley graphs of dihedral groups

Abstract

A connected graph $\Gamma$ of diameter $\mathrm{diam}(\Gamma )\ge \ell$ is $\ell$-distance-balanced if $|W_{xy}(\Gamma )|=|W_{yx}(\Gamma )|$ for every $x,y\in V(\Gamma )$ with $d_{\Gamma }(x,y)=\ell$, where $W_{xy}(\Gamma )$ is the set of vertices of $\Gamma$ that are closer to $x$ than to $y$. $\Gamma$ is said to be highly distance-balanced if it is $\ell$-distance-balanced for every $\ell \in [\mathrm{diam}(\Gamma )]$. It is proved that every cubic Cayley graph whose generating set is one of $\{a,a^{n-1},b{a}^r\}$ and $\{a^k,a^{n-k},b{a}^t\}$ is highly distance-balanced. This partially solves a problem posed by Miklavič and Šparl.