Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of shortest path lengths). Then the sequence $\{k_i\}_{0\leq i\leq d}$, where $d$ is the diameter of the graph, is unimodal (see e.g. Taylor and Levingston's paper for details).

Are there other classes of regular graphs with that property?

  • $\begingroup$ Almost all regular graphs, I believe, though I don't know if it has been proved. $\endgroup$ – Brendan McKay May 20 '14 at 11:02

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.