Книга (теория графов)

Книга треугольников

Книга (часто записывается $B_p$ ) может быть любым графом некоторого вида, который образован циклами, имеющими общее ребро.

Вариации

Один вид, который может быть назван книгой четырёхугольников, состоит из p четырёхугольников, имеющих общее ребро (известное как «корешок» или «база» книги). То есть это прямое произведение звезды и отдельного ребраШаблон:Sfn. 7-Страничная книга этого типа даёт пример графа без гармоничной разметкиШаблон:Sfn.

Второй вид, который может быть назван книгой треугольников или треугольной книгой, является полным двудольным графом K_1,1,p. Это граф, состоящий из $p$ треугольников, имеющих общее реброШаблон:Sfn. Книга этого типа является расщепляемым графом. Этот граф можно также назвать $K_e(2,p)$Шаблон:Sfn. Книги треугольников образуют один из ключевых блоков рёберно совершенных графовШаблон:Sfn.

Термин «граф-книга» использовался для других целей. Так, БариолиШаблон:Sfn использовал его для графов, составленных из произвольных подграфов, имеющих две общие вершины. (Бариоли не использовал обозначение $B_p$ для этих графов-книг.)

Внутри больших графов

Если дан граф $G$, можно записать $bk(G)$ для наибольшей книги (рассматриваемого типа), содержащейся в $G$.

Теоремы о книгах

Обозначим число Рамсея двух треугольных книг $r(B_p,B_q).$ Это наименьшее число $r$, такое, что для лютого графа с $r$ вершинами либо сам граф содержит $B_p$ в качестве подграфа, либо его дополнение содержит $B_q$ в качестве подграфа.

• Если $1⩽p⩽q$, то $r(B_p,B_q)=2q+3$ (доказали Руссо и Шихан).
• Существует константа $c=o(1)$, такая, что $r(B_p,B_q)=2q+3$, когда $q⩾cp$.
• Если $p⩽q/6+o(q)$ и $q$ достаточно большое, число Рамсея задаётся формулой $2q+3$.
• Пусть $C$ — константа, и $k=Cn$. Тогда любой граф с $n$ вершинами и $m$ рёбрами содержит (книгу треугольников) $B_k$Шаблон:Sfn.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья