书 (图论)

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

一个三角形书

种类

由$p$个共享一条边（称为书的“脊”或“基”）的四边形组成的书称为四边形书。也就是说，它是一个星图和一条单边的笛卡尔积。这种类型的7页书图提供了一个没有协调标号的图的例子。

由$p$个共享一条边的三角形组成的书称为三角形书，其可用完全三部图K_1,1,p表示。 这种类型的书属于分割图。这种图也称为 $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}$。