在数学、计算机科学和信息处理领域，有几种被称为“星形图”的图。最常见的星形图是 
-星形图 
，定义为完全二分图 
。
一种完全不同的 
-星形图，这里称为 
-排列星形图 
（等同于 
-排列图），被定义为顶点是 
个排列的图，其中当两个排列通过交换一对元素相关联时，顶点之间通过边连接（Akers 等，1987；Akl 和 Qiu，1991；Palis 等，1994；Rajasekaran 和 Wei，1997）。这种图是 正则 的，顶点度数为 
，图直径为 
（Akers 等，1987；Rajasekaran 和 Wei，1997），其中 
是向下取整函数。它们也是顶点传递的、边传递的和弧传递的。
Chiang 和 Chen（1995）考虑了 
对 
-排列星形图的推广。这种类型的图包括 
-排列星形图 
（以及因此的排列图 
）作为特例 
。
排列星形图 
是正则的，顶点度数为 
，具有 顶点计数 
，图直径为
 |
(1)
|
（Chiang 和 Chen，1995）。当 
时，
是顶点传递的，但既不是边传递的也不是弧传递的。
（n,k）-排列星形图在 Wolfram 语言中实现为GraphData[
"PermutationStar", 
n, k
].
特殊情况如上图所示，并在下表中进行了总结。
-Cube." In Proc. International Conference of Parallel Processing, pp. 393-400, 1987.Akl, S. G. and Qiu, K. "Data Communication and Computational Geometry on the Star and Pancake Interconnection Networks." Technical Report TR 91-301, Dept. of Computing and Information Science, Queen's University at Kingston, Ontario, Canada. May 1991.Chiang, W.-K. and Chen, R.-J. "The 
-Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.Palis, M.; Rajasekaran, S.; and Wei, D. S. L. "Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks." J. Parallel Distrib. Comput. 20, 145-157, 1994.Rajasekaran, S. and Wei, D. S. L. "Selection, Routing, and Sorting on the Star Graph." J. Parallel Distrib. Comput. 41, 225-233, 1997.