書 (圖論)
在圖論中,書圖(book graph,常寫作 )是由多個環經過同一條邊而形成的圖。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Graph_book_sample.gif/220px-Graph_book_sample.gif)
種類 編輯
由 個共享一條邊(稱為書的「脊」或「基」)的四邊形組成的書稱為四邊形書。也就是說,它是一個星圖和一條單邊的笛卡爾積。[1][2]這種類型的7頁書圖提供了一個沒有協調標號的圖的例子。[2]
由 個共享一條邊的三角形組成的書稱為三角形書,其可用完全三部圖K1,1,p表示。[3] 這種類型的書屬於分割圖。這種圖也稱為 。[4] 三角形書是線完美圖的一個關鍵構建模塊。[5]
術語"書圖"曾用於其他用途。 Barioli曾將該詞用於表示由具有兩個共同頂點的多個子圖組成的圖。[6](但他沒有用到 這個代號)
書的最大圖 編輯
給出一個圖 ,能包含 的最大書圖可記作 。
書的定理 編輯
可定義滿足拉姆齊數的兩個三角形書為 。當 取最小值時,任意一個有 個頂點的圖中,該圖不是本身包含子圖 就是它的補圖包含子圖 。
參考文獻 編輯
- ^ Weisstein, Eric W. (編). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語).
- ^ 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). (頁面存檔備份,存於網際網路檔案館)
- ^ 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.
- ^ Erdős, Paul. On the structure of linear graphs. Israel Journal of Mathematics. 1963, 1: 156–160. doi:10.1007/BF02759702.
- ^ 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..
- ^ 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.
- ^ 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.
- ^ Erdős, P. On a theorem of Rademacher-Turán. Illinois Journal of Mathematics. 1962, 6: 122–7 [2019-05-28]. (原始內容存檔於2020-07-26). (頁面存檔備份,存於網際網路檔案館)