On the Problem of Determining which (n, k)-Star Graphs are Cayley Graphs

详细信息    查看全文

• 作者：Eddie Cheng ; Li Li ; László Lipták ; Sangho Shim…
• 关键词：Interconnection networks ; Cayley graphs ; Vertex ; forwarding index ; (n ; k) ; star graphs
• 刊名：Graphs and Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：85-102
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Engineering Design;
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：33

文摘

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.