Книга (теория графов)
Книга (часто записывается [math]\displaystyle{ B_p }[/math] ) может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.
Вариации
Один вид, который может быть назван книгой четырёхугольников, состоит из p четырёхугольников, имеющих общее ребро (известное как «корешок» или «база» книги). То есть это прямое произведение звезды и отдельного ребра[1][2]. 7-Страничная книга этого типа даёт пример графа без гармоничной разметки[2].
Второй вид, который может быть назван книгой треугольников или треугольной книгой, является полным двудольным графом K1,1,p. Это граф, состоящий из [math]\displaystyle{ p }[/math] треугольников, имеющих общее ребро[3]. Книга этого типа является расщепляемым графом. Этот граф можно также назвать [math]\displaystyle{ K_e(2,p) }[/math][4]. Книги треугольников образуют один из ключевых блоков рёберно совершенных графов[5].
Термин «граф-книга» использовался для других целей. Так, Бариоли[6] использовал его для графов, составленных из произвольных подграфов, имеющих две общие вершины. (Бариоли не использовал обозначение [math]\displaystyle{ B_p }[/math] для этих графов-книг.)
Внутри больших графов
Если дан граф [math]\displaystyle{ G }[/math], можно записать [math]\displaystyle{ bk(G) }[/math] для наибольшей книги (рассматриваемого типа), содержащейся в [math]\displaystyle{ G }[/math].
Теоремы о книгах
Обозначим число Рамсея двух треугольных книг [math]\displaystyle{ r(B_p,\ B_q). }[/math] Это наименьшее число [math]\displaystyle{ r }[/math], такое, что для лютого графа с [math]\displaystyle{ r }[/math] вершинами либо сам граф содержит [math]\displaystyle{ B_p }[/math] в качестве подграфа, либо его дополнение содержит [math]\displaystyle{ B_q }[/math] в качестве подграфа.
- Если [math]\displaystyle{ 1\leqslant p\leqslant q }[/math], то [math]\displaystyle{ r(B_p,\ B_q)=2q+3 }[/math] (доказали Руссо и Шихан).
- Существует константа [math]\displaystyle{ c=o(1) }[/math], такая, что [math]\displaystyle{ r(B_p,\ B_q)=2q+3 }[/math], когда [math]\displaystyle{ q\geqslant cp }[/math].
- Если [math]\displaystyle{ p\leqslant q/6+o(q) }[/math] и [math]\displaystyle{ q }[/math] достаточно большое, число Рамсея задаётся формулой [math]\displaystyle{ 2q+3 }[/math].
- Пусть [math]\displaystyle{ C }[/math] — константа, и [math]\displaystyle{ k=Cn }[/math]. Тогда любой граф с [math]\displaystyle{ n }[/math] вершинами и [math]\displaystyle{ m }[/math] рёбрами содержит (книгу треугольников) [math]\displaystyle{ B_k }[/math][7].
Примечания
- ↑ Weisstein, Eric W. Book Graph (англ.) на сайте Wolfram MathWorld.
- ↑ 2,0 2,1 Gallian, 1998, с. Dynamic Survey 6.
- ↑ Shi, Song, 2007, с. 526—529.
- ↑ Erdős, 1963, с. 156–160.
- ↑ Maffray, 1992, с. 1–8.
- ↑ Barioli, 1998, с. 11–31.
- ↑ Erdős, 1962, с. 122—127.
Литература
- Joseph Gallian. A dynamic survey of graph labeling // Electronic Journal of Combinatorics. — 1998. — Т. 5.
- 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. — doi:10.1016/j.laa.2006.08.007.
- Paul Erdős. On the structure of linear graphs // Israel Journal of Mathematics. — 1963. — Т. 1. — doi:10.1007/BF02759702.
- Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вып. 1. — С. 1–8. — doi:10.1016/0095-8956(92)90028-V.
- Francesco Barioli. Completely positive matrices with a book-graph // Linear Algebra and its Applications. — 1998. — Т. 277. — doi:10.1016/S0024-3795(97)10070-2.
- Erdős P. On a theorem of Rademacher-Turán // Illinois Journal of Mathematics. — 1962. — Т. 6.
Для улучшения этой статьи желательно: |