书 (图论)

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

一个三角形书

种类

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

由${\displaystyle p}$ 个共享一条边的三角形组成的书称为三角形书，其可用完全三部图K_1,1,p表示。^[3] 这种类型的书属于分割图。这种图也称为 ${\displaystyle K_{e}(2,p)}$ 。^[4] 三角形书是线完美图的一个关键构建模块。^[5]

术语"书图"曾用于其他用途。 Barioli曾将该词用于表示由具有两个共同顶点的多个子图组成的图。^[6]（但他没有用到${\displaystyle B_{p}}$ 这个代号）

书的最大图

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

书的定理

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

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

参考文献

1. Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）. 
2. Gallian, Joseph A. A dynamic survey of graph labeling. Electronic Journal of Combinatorics. 1998, 5: Dynamic Survey 6 [2019-05-28]. MR 1668059. （原始内容于2019-11-08）.  （页面存档备份，存于互联网档案馆）
3. Lingsheng Shi; Zhipeng Song. Upper bounds on the spectral radius of book-free and/or K_2,l-free graphs. Linear Algebra and its Applications. 2007, 420: 526–9. doi:10.1016/j.laa.2006.08.007. 
4. Erdős, Paul. On the structure of linear graphs. Israel Journal of Mathematics. 1963, 1: 156–160. doi:10.1007/BF02759702. 
5. Maffray, Frédéric. Kernels in perfect line-graphs. Journal of Combinatorial Theory. Series B. 1992, 55 (1): 1–8. MR 1159851. doi:10.1016/0095-8956(92)90028-V. .
6. Barioli, Francesco. Completely positive matrices with a book-graph. Linear Algebra and its Applications. 1998, 277: 11–31. doi:10.1016/S0024-3795(97)10070-2. 
7. Rousseau, C. C.; Sheehan, J. On Ramsey numbers for books. Journal of Graph Theory. 1978, 2 (1): 77–87. MR 0486186. doi:10.1002/jgt.3190020110. 
8. Erdős, P. On a theorem of Rademacher-Turán. Illinois Journal of Mathematics. 1962, 6: 122–7 [2019-05-28]. （原始内容于2020-07-26）.  （页面存档备份，存于互联网档案馆）