書 (圖論)

圖論中,書圖book graph,常寫作 )是由多個經過同一條邊而形成的圖。

一個三角形書

種類

 個共享一條邊(稱為書的「脊」或「基」)的四邊形組成的書稱為四邊形書。也就是說,它是一個星圖和一條單邊的笛卡爾積[1][2]這種類型的7頁書圖提供了一個沒有協調標號的圖的例子。[2]

 個共享一條邊的三角形組成的書稱為三角形書,其可用完全三部圖K1,1,p表示。[3] 這種類型的書屬於分割圖。這種圖也稱為  [4] 三角形書是線完美圖的一個關鍵構建模塊。[5]

術語"書圖"曾用於其他用途。 Barioli曾將該詞用於表示由具有兩個共同頂點的多個子圖組成的圖。[6](但他沒有用到 這個代號)

書的最大圖

給出一個圖 ,能包含 的最大書圖可記作 

書的定理

可定義滿足拉姆齊數的兩個三角形書為 。當 取最小值時,任意一個有 個頂點的圖中,該圖不是本身包含子圖 就是它的補圖包含子圖 

  • 如果  ,那麼 [7]
  •  時,存在一個常數 使得 
  • 如果  並且 數值較大,拉姆齊數的值為 
  •  取為常數,並且取 。那麼每一個有 個頂點和 條邊的圖都包含(三角形) [8]

參考文獻

  1. ^ Weisstein, Eric W. (編). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  2. ^ 2.0 2.1 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 K2,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). 頁面存檔備份,存於互聯網檔案館