查看“︁书 (图论)”︁的源代码

[[File:Graph_book_sample.gif|缩略图|一个三角形书]]
在[[图论]]中，'''书图'''（'''book graph'''，常写作<math>B_p</math>&nbsp;）是由多个[[環 (圖論)|环]]经过同一条边而形成的图。

== 种类 ==
由''<math>p</math>''个共享一条边（称为书的“脊”或“基”）的[[四边形]]组成的书称为'''四边形书'''。也就是说，它是一个[[星 (图论)|星图]]和一条单边的[[笛卡尔积]]。<ref>{{cite mathworld|id=BookGraph|title=Book Graph}}</ref><ref name="gallian">{{Cite journal|title=A dynamic survey of graph labeling|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6|last=Gallian|first=Joseph A.|authorlink=Joseph Gallian|journal=[[Electronic Journal of Combinatorics]]|year=1998|volume=5|page=Dynamic Survey 6|mr=1668059|access-date=2019-05-28|archive-date=2019-11-08|archive-url=https://web.archive.org/web/20191108105416/https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6|dead-url=no}} {{Wayback|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6 |date=20191108105416 }}</ref>这种类型的7页书图提供了一个没有[[图标号|协调标号]]的图的例子。<ref name="gallian" />

由''<math>p</math>''个共享一条边的[[三角形]]组成的书称为'''三角形书'''，其可用完全三部图''K''<sub>1,1,''p''</sub>表示。<ref>{{Cite journal|title=Upper bounds on the spectral radius of book-free and/or ''K''<sub>2,l</sub>-free graphs|url=https://archive.org/details/sim_linear-algebra-and-its-applications_2007-01-15_420_2-3/page/n289|last=Lingsheng Shi|last2=Zhipeng Song|journal=Linear Algebra and its Applications|doi=10.1016/j.laa.2006.08.007|year=2007|volume=420|pages=526–9}}</ref> 这种类型的书属于[[Split graph|分割图]]。这种图也称为 <math>K_e(2,p)</math>。<ref>{{Cite journal|title=On the structure of linear graphs|last=Erdős|first=Paul|authorlink=Paul Erdős|journal=Israel Journal of Mathematics|doi=10.1007/BF02759702|year=1963|volume=1|pages=156–160}}</ref> 三角形书是[[Line perfect graph|线完美图]]的一个关键构建模块。<ref>{{Cite journal|title=Kernels in perfect line-graphs|last=Maffray|first=Frédéric|journal=[[Journal of Combinatorial Theory]]|issue=1|doi=10.1016/0095-8956(92)90028-V|year=1992|series=Series B|volume=55|pages=1–8|mr=1159851}}.</ref>

术语"书图"曾用于其他用途。 Barioli曾将该词用于表示由具有两个共同顶点的多个子图组成的图。<ref>{{Cite journal|title=Completely positive matrices with a book-graph|url=https://archive.org/details/sim_linear-algebra-and-its-applications_1998-06-15_277/page/n20|last=Barioli|first=Francesco|journal=Linear Algebra and its Applications|doi=10.1016/S0024-3795(97)10070-2|year=1998|volume=277|pages=11–31}}</ref>（但他没有用到<math>B_p</math>这个代号）

== 书的最大图 ==
给出一个图<math>G</math>，能包含<math>G</math>的最大书图可记作<math>bk(G)</math>。

== 书的定理 ==
可定义满足[[拉姆齐定理|拉姆齐数]]的两个三角形书为<math>r(B_p,\ B_q)</math>。当<math>r</math>取最小值时，任意一个有<math>r</math>个顶点的图中，该图不是本身包含子图<math>B_p</math>就是它的[[補圖|补图]]包含子图<math>B_q</math>。

* 如果 <math>1\leq p\leq q</math>，那么<math>r(B_p,\ B_q)=2q+3</math>。<ref>{{Cite journal|title=On Ramsey numbers for books|url=https://archive.org/details/sim_journal-of-graph-theory_spring-1978_2_1/page/77|last=Rousseau|first=C. C.|last2=Sheehan|first2=J.|journal=[[Journal of Graph Theory]]|issue=1|doi=10.1002/jgt.3190020110|year=1978|volume=2|pages=77–87|mr=486186}}</ref>
* 当<math>q\geq cp</math>时，存在一个常数<math>c=o(1)</math>使得<math>r(B_p,\ B_q)=2q+3</math>。
* 如果 <math> p\leq q/6+o(q)</math>并且<math>q</math>数值较大，[[拉姆齐定理|拉姆齐数]]的值为<math>2q+3</math>。
* 将<math>C</math>取为常数，并且取<math>k = Cn</math>。那么每一个有<math>n</math>个顶点和<math>m</math>条边的图都包含(三角形)<math>B_k</math>。<ref>{{Cite journal|title=On a theorem of Rademacher-Turán|url=http://projecteuclid.org/euclid.ijm/1255631811|last=Erdős|first=P.|journal=Illinois Journal of Mathematics|year=1962|volume=6|pages=122–7|access-date=2019-05-28|archive-date=2020-07-26|archive-url=https://web.archive.org/web/20200726105406/https://projecteuclid.org/euclid.ijm/1255631811|dead-url=no}} {{Wayback|url=http://projecteuclid.org/euclid.ijm/1255631811 |date=20200726105406 }}</ref>

== 参考文献 ==
{{Reflist}}
[[Category:图论]]
[[Category:有未审阅翻译的页面]]