文摘
In this paper we work to classify which of the (n, k)-star graphs, denoted by \(S_{n,k}\), are Cayley graphs. Although the complete classification is left open, we derive infinite and non-trivial classes of both Cayley and non-Cayley graphs. We give a complete classification of the case when \(k=2\), showing that \(S_{n,2}\) is Cayley if and only if n is a prime power. We also give a sufficient condition for \(S_{n,3}\) to be Cayley and study other structural properties, such as demonstrating that \(S_{n,k}\) always has a uniform shortest path routing.