Книга (часто записується ) — будь-який з графів, який утворений з циклів, що мають спільне ребро.
Варіації Один вид, який можна назвати книгою чотирикутників, складається з p чотирикутників, що мають спільне ребро (відоме як «корінець» або «база» книги). Тобто це прямий добуток зірки і окремого ребра. 7-сторінкова книга цього типу є прикладом графу без гармонійної розмітки.
Другий вид, який можна назвати книгою трикутників або трикутною книгою, є повним двочастковим графом K1,1,p. Це граф, що складається з трикутників, що мають спільне ребро. Книга цього типу є розщеплюваним графом. Цей граф можна також назвати . Книги трикутників утворюють один з ключових блоків реберно-досконалих графів.
Термін «граф-книга» використовувався для інших цілей. Так, Баріолі використовував його для графів, складених з довільних підграфів, що мають дві спільні вершини. (Баріолі для цих графів-книг не використовував позначення .)
Всередині більших графів Якщо дано граф , можна записати для найбільшої книги (розглянутого типу), що міститься в .
Теореми про книги Позначивши число Рамсея двох трикутних книг Це найменше число , таке, що для будь-якого графу з вершинами або сам граф містить як підграф, або його доповнення містить як підграф.
Якщо , то (довели Руссо і Шихан). Існує стала , така, що , коли . Якщо і досить велике, число Рамсея задається формулою . Нехай — стала, і . Тоді будь-який граф з вершинами і ребрами містить книгу трикутників .
Примітка
Література