主題
Search

書圖


BookGraph

m-書圖定義為圖的笛卡爾積 B_m=S_(m+1) square P_2,其中 S_m 是一個星圖P_2 是兩個節點的路徑圖。書圖推廣到 n 個“堆疊”頁面的情況是 (m,n)-堆疊書圖

m-書圖的特殊情況總結如下。

書圖的預計算屬性在 Wolfram 語言中實現為GraphData[{"Book", m}].

書圖 B_n單純形圖,其對應於星圖 S_(n+1)=K_(1,n)

形式為 B_(4k+3) 的書圖不滿足優美性的奇偶性條件,因此是非優美的 (Gallian 2018)。Maheo (1980) 證明了 B_(2k)優美的,並推測 B_(4k+1) 對於所有正整數 n 都是優美的。Delorme (1980) 為 B_(2k) 提供了更簡單的優美標號,併為 B_(4k+1) 提供了優美標號,從而證實了該推測。

書圖 S_(n+1) square P_2 具有色多項式獨立多項式匹配多項式秩多項式,由下式給出

pi(x)=(x-1)x(x^2-3x+3)^n
(1)
I(x)=2x(1+x)^n+(1+2x)^n
(2)
mu(x)=(x-1)^(n-2)(x+1)^(n-2)[n^2x^2+(x^2-1)^3+n(-1+2x^2-2x^4)]
(3)
R(x,y)=([1+3x(x+1)]^n(y-x)+x(y+1){1+x[3+x(3+y)]}^n)/y.
(4)

相應的遞推關係是

pi_n(z)=(z^2-3z+3)pi_(n-1)(z)
(5)
I_n(x)=(3x+2)I_(n-1)(x)-(x+1)(2x+1)I_(n-2)(x)
(6)
mu_n(x)=3mu_(n-1)(x)-3mu_(n-2)(x)+mu_(n-3)(x)
(7)
R_n(x,y)=(x^2y+6x^2+6x+2)R_(n-1)(x,y)-(3x^2+3x+1)(x^2y+3x^2+3x+1)R_(n-2)(x,y).
(8)

另請參閱

圖的笛卡爾積, 堆疊書圖, 星圖

使用 探索

參考文獻

Delorme, D. "Two Sets of Graceful Graphs." J. Graph Th. 4, 247-250, 1980.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Maheo, M. "Strongly Graceful Graphs." Disc. Math. 29, 39-46, 1980.White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, p. 49, 2001.

在 中被引用

書圖

引用為

Weisstein, Eric W. "書圖。" 來自 網路資源。 https://mathworld.tw/BookGraph.html

主題分類