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

Книга трикутників

Книга (часто записується $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.

Література

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