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

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

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

Варианты [ править ]

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

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

Термин «книжная диаграмма» использовался и для других целей. Бариоли ^[7] использовал его для обозначения графа, состоящего из ряда произвольных подграфов, имеющих две общие вершины. (Бариоли не писал для своего книжного графика.)${\ 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}}$

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

Ссылки [ править ]