書 (圖論)

一個三角形書

在圖論中，書圖（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}$。