书 (图论)

图论中,书图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). 页面存档备份,存于互联网档案馆