皇冠圖 -- 來自 - 數學天地

皇冠圖

對於整數，-皇冠圖是具有頂點集的圖

${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，出自“整數序列線上百科全書”。

皇冠圖