书 (图论)

在图论中，书图（book graph，常写作B_p ）是由多个环经过同一条边而形成的图。

种类
由p个共享一条边（称为书的“脊”或“基”）的四边形组成的书称为四边形书。也就是说，它是一个星图和一条单边的笛卡尔积。这种类型的7页书图提供了一个没有协调标号的图的例子。 这种类型的书属于分割图。这种图也称为 K_e(2,p)。 三角形书是线完美图的一个关键构建模块。

术语"书图"曾用于其他用途。 Barioli曾将该词用于表示由具有两个共同顶点的多个子图组成的图。（但他没有用到B_p这个代号）

书的最大图
给出一个图G，能包含G的最大书图可记作bk(G)。

书的定理
可定义满足拉姆齐数的两个三角形书为r(B_p,\ B_q)。当r取最小值时，任意一个有r个顶点的图中，该图不是本身包含子图B_p就是它的补图包含子图B_q。

• 如果 1\leq p\leq q，那么r(B_p,\ B_q)=2q+3。
• 当q\geq cp时，存在一个常数c=o(1)使得r(B_p,\ B_q)=2q+3。
• 如果 p\leq q/6+o(q)并且q数值较大，拉姆齐数的值为2q+3。
• 将C取为常数，并且取k = Cn。那么每一个有n个顶点和m条边的图都包含(三角形)B_k。

参考文献