主题
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)

另请参阅

图的笛卡尔积, 堆叠书图, 星图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

书图

引用为

Weisstein, Eric W. "书图。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/BookGraph.html

主题分类