皇冠图 -- 来自 Wolfram MathWorld

皇冠图

对于整数，-皇冠图是具有顶点集的图

${x_0,x_1,...,x_(n-1),y_0,y_1,...,y_(n-1)}$

(1)

和边集

${(x_i,y_j):0<=i,j<=n-1,i!=j}.$

(2)

因此，它等价于移除了水平边的完全二部图。

请注意，“皇冠图”一词也曾用于指代日晒图（例如，Gallian 2018）。

-皇冠图与车互补图同构（Brouwer et al. 1989，第 222 页，定理 7.5.2，项目 (iii) 中有些令人困惑地表述为网格的补图），其中表示图的笛卡尔积。-皇冠图也与完全二部图减去独立边集同构（参见 Brouwer 和 Koolen 1999）。

皇冠图是距离传递的（Brouwer et al. 1989，第 222 页），因此也是距离正则的。它们也是泰勒图。

-皇冠图的线图是排列图。

-皇冠图与哈尔图同构。其他特殊情况总结在下表中。

中的顶点数为，边数为。

对于 , 4, 5, ...，有向哈密顿圈的数量由 2, 12, 312, 9600, 416880, ... (OEIS A094047) 给出，它具有优美的闭合形式

(3)

（M. Alekseyev，私人通信，2 月 10 日，2008 年）。

对于的 -图圈的数量的闭合公式由（对于为奇数）和

（E. Weisstein，2014 年 11 月 16 日）。

-皇冠图的独立多项式是

(7)

它满足递推方程

(8)

参考文献

Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. 距离正则图。 纽约：Springer-Verlag，1989 年。

Brouwer, A. 和 Koolen, J. "价数为 4 的距离正则图。" J. Algebraic Combin. 10, 5-24, 1999.

Sloane, N. J. A. 序列 A002378/M1581 和 A094047，出自“整数序列在线百科全书”。

皇冠图