Книга (теория графов) - Book (graph theory)

Треугольная книга

В теория графов, а книжный график (часто пишется ${ displaystyle B_ {p}}$ ) может быть любым из нескольких видов графа, образованного несколькими циклами, разделяющими ребро.

Вариации

Один вид, который можно назвать четырехугольная книга, состоит из п четырехугольники имеющие общий край (известный как «корешок» или «основа» книги). То есть это Декартово произведение из звезда и один край.^[1]^[2] 7-страничная книжная диаграмма этого типа представляет собой пример диаграммы без гармоничная маркировка.^[2]

Второй тип, который можно было бы назвать треугольная книга, - полный трехчастный граф K_1,1,п. Это граф, состоящий из ${ displaystyle p}$ треугольники разделяя общее преимущество.^[3] Книга такого типа - это разделенный график. Этот граф также называют ${ displaystyle K_ {e} (2, p)}$ .^[4] Треугольные книги - один из ключевых строительных блоков линейные идеальные графики.^[5]

Термин «книжная диаграмма» использовался и для других целей. Бариоли^[6] использовал его для обозначения графа, состоящего из ряда произвольных подграфов, имеющих две общие вершины. (Бариоли не писал ${ displaystyle B_ {p}}$ за его книжку-график.)

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

Учитывая график ${ displaystyle G}$ можно написать ${ displaystyle bk (G)}$ за самую большую книгу (рассматриваемого типа), содержащуюся в ${ displaystyle G}$ .

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

Обозначим Число Рамсея двух треугольных книг ${ displaystyle r (B_ {p}, B_ {q}).}$ Это наименьшее число ${ displaystyle r}$ так что для каждого ${ displaystyle r}$ -вершинный граф, либо сам граф содержит ${ displaystyle B_ {p}}$ как подграф, или его дополнительный граф содержит ${ displaystyle B_ {q}}$ как подграф.

Если ${ displaystyle 1 leq p leq q}$ , тогда ${ Displaystyle г (B_ {p}, B_ {q}) = 2q + 3}$ .^[7]
Существует постоянная ${ Displaystyle с = о (1)}$ такой, что ${ Displaystyle г (B_ {p}, B_ {q}) = 2q + 3}$ в любое время ${ displaystyle q geq cp}$ .
Если ${ Displaystyle п leq q / 6 + о (д)}$ , и ${ displaystyle q}$ большой, Число Рамсея дан кем-то ${ displaystyle 2q + 3}$ .
Позволять ${ displaystyle C}$ быть константой, и ${ displaystyle k = Cn}$ . Тогда каждый граф на ${ displaystyle n}$ вершины и ${ displaystyle m}$ ребра содержит (треугольную) ${ displaystyle B_ {k}}$ .^[8]