齿轮图,有时也称为二部轮图(Brandstädt et al. 1987),是一个轮图,其外循环的每对相邻图顶点之间添加了一个图顶点(Gallian 2018)。齿轮图 有 个节点和 条边。
齿轮图 是 贾汉吉尔图 的一个特例 。
通过从火柴棍嵌入中获取顶点集,并将所有间隔单位距离的顶点对连接起来,可以生成有吸引力的派生单位距离图,如上面所示的 、6、12 和 18 的情况,其中 的情况对应于轮图 。
Ma 和 Feng (1984) 证明了所有齿轮图都是优美图,Liu (1996) 表明,如果在轮图的外循环的每对顶点之间插入两个或多个顶点,则生成的图也是优美图(Gallian 2018)。
齿轮图的预计算属性在 Wolfram 语言中由以下给出:GraphData["Gear", n].
齿轮图具有色多项式、独立多项式、匹配多项式、秩多项式和可靠性多项式,由以下给出:
(1)
| |||
(2)
| |||
(3)
| |||
(4)
| |||
(5)
|
其中 。这些具有递推方程
(6)
| |||
(7)
| |||
(8)
| |||
(9)
| |||
(10)
|