Книга (теория графов)
Книга (часто записывается B p {displaystyle B_{p}} ) может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.
Вариации
Один вид, который может быть назван книгой четырёхугольников, состоит из p четырёхугольников, имеющих общее ребро (известное как «корешок» или «база» книги). То есть это прямое произведение звезды и отдельного ребра. 7-Страничная книга этого типа даёт пример графа без гармоничной разметки.
Второй вид, который может быть назван книгой треугольников или треугольной книгой, является полным двудольным графом K1,1,p. Это граф, состоящий из p {displaystyle p} треугольников, имеющих общее ребро. Книга этого типа является расщепляемым графом. Этот граф можно также назвать K e ( 2 , p ) {displaystyle K_{e}(2,p)} . Книги треугольников образуют один из ключевых блоков рёберно совершенных графов.
Термин «граф-книга» использовался для других целей. Так, Бариоли использовал его для графов, составленных из произвольных подграфов, имеющих две общие вершины. (Бариоли не использовал обозначение B p {displaystyle B_{p}} для этих графов-книг.)
Внутри больших графов
Если дан граф G {displaystyle G} , можно записать b k ( G ) {displaystyle bk(G)} для наибольшей книги (рассматриваемого типа), содержащейся в G {displaystyle G} .
Теоремы о книгах
Обозначим число Рамсея двух треугольных книг r ( B p , B q ) . {displaystyle r(B_{p}, B_{q}).} Это наименьшее число r {displaystyle r} , такое, что для лютого графа с r {displaystyle r} вершинами либо сам граф содержит B p {displaystyle B_{p}} в качестве подграфа, либо его дополнение содержит B q {displaystyle B_{q}} в качестве подграфа.
- Если 1 ⩽ p ⩽ q {displaystyle 1leqslant pleqslant q} , то r ( B p , B q ) = 2 q + 3 {displaystyle r(B_{p}, B_{q})=2q+3} (доказали Руссо и Шихан).
- Существует константа c = o ( 1 ) {displaystyle c=o(1)} , такая, что r ( B p , B q ) = 2 q + 3 {displaystyle r(B_{p}, B_{q})=2q+3} , когда q ⩾ c p {displaystyle qgeqslant cp} .
- Если p ⩽ q / 6 + o ( q ) {displaystyle pleqslant q/6+o(q)} и q {displaystyle q} достаточно большое, число Рамсея задаётся формулой 2 q + 3 {displaystyle 2q+3} .
- Пусть C {displaystyle C} — константа, и k = C n {displaystyle k=Cn} . Тогда любой граф с n {displaystyle n} вершинами и m {displaystyle m} рёбрами содержит (книгу треугольников) B k {displaystyle B_{k}} .
