Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В теории графов книжный граф (часто обозначаемый как) может быть одним из нескольких типов графов, образованных несколькими циклами, разделяющими ребро.
In graph theory, a book graph (often written ) may be any of several kinds of graph formed by multiple cycles sharing an edge.
Вариации
Один вид, который можно назвать четырехугольной книгой, состоит из *p* четырехугольников, имеющих общий край (известный как "спина" или "база" книги). То есть, это декартово произведение звезды и одного ребра. Книга на 7 страницах такого типа является примером графа, не имеющего гармонической раскраски. Книга такого типа является расщепленным графом. Этот граф также называют графом тагомизатора (по названию тагомизаторов, шипованных хвостов стегозавров, из-за их заостренного вида на некоторых рисунках), а их графические матроиды – тагомизаторными матроидами. Треугольные книги формируют один из ключевых строительных блоков линейно совершенных графов. Термин "книжный граф" используется и в других значениях. Бариоли использовал его для обозначения графа, составленного из ряда произвольных подграфов, имеющих две общие вершины. (Бариоли не использовал обозначение для своего книжного графа.)
One kind, which may be called a quadrilateral book, consists of p quadrilaterals sharing a common edge (known as the "spine" or "base" of the book). That is, it is a Cartesian product of a star and a single edge. The 7 page book graph of this type provides an example of a graph with no harmonious labeling. A book of this type is a split graph. This graph has also been called a or a thagomizer graph (after thagomizers, the spiked tails of stegosaurian dinosaurs, because of their pointy appearance in certain drawings) and their graphic matroids have been called thagomizer matroids. Triangular books form one of the key building blocks of line perfect graphs. The term "book graph" has been employed for other uses. Barioli used it to mean a graph composed of a number of arbitrary subgraphs having two vertices in common. (Barioli did not write for his book graph.)
Внутри больших графиков
Для заданного графа можно записать наибольшую книгу (рассматриваемого типа), содержащуюся в нем.
Given a graph , one may write for the largest book (of the kind being considered) contained within .
Теоремы в книгах
Обозначим число Рамзи для двух треугольников через R(3,3). Это наименьшее число n, такое, что для любого графа с n вершинами, либо сам граф содержит треугольник в качестве подграфа, либо его дополнение содержит треугольник в качестве подграфа. Если n = 6, то R(3,3) = 6. Существует константа c, такая, что R(3,3) ≥ c * n, когда n стремится к бесконечности. Если n велико, число Рамзи приблизительно равно n²/log₂n. Пусть c – константа, и m = c * n. Тогда любой граф с n вершинами и m ребрами содержит треугольник.
Denote the Ramsey number of two triangular books by This is the smallest number such that for every vertex graph, either the graph itself contains as a subgraph, or its complement graph contains as a subgraph. If , then There exists a constant such that whenever If , and is large, the Ramsey number is given by Let be a constant, and Then every graph on vertices and edges contains a (triangular) .