書 (圖論)

在圖論中，書圖（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]