Граф Хенсона
В теории графов граф Хенсона G i — это неориентированный бесконечный граф , единственный счетный однородный граф , который не содержит i -вершинную клику , но содержит все K i -свободные конечные графы в качестве индуцированных подграфов. Например, G 3 — граф без треугольников , который содержит все конечные графы без треугольников.
Эти графы названы в честь К. Уорда Хенсона, опубликовавшего их конструкцию (для всех i ≥ 3 ) в 1971 году. [1] Первый из этих графов, G 3 , также называют однородным графом без треугольников или универсальным графом без треугольников .
Строительство
[ редактировать ]Чтобы построить эти графы, Хенсон упорядочивает вершины графа Радо в последовательность со свойством, что для каждого конечного набора S вершин существует бесконечное количество вершин, имеющих S в качестве набора предыдущих соседей. (Существование такой последовательности однозначно определяет граф Радо.) Затем он определяет G i как индуцированный подграф графа Радо, образованный удалением последней вершины (в порядке последовательности) каждой i -клики графа Радо. [1]
При такой конструкции каждый граф G i является индуцированным подграфом G i + 1 , а объединение этой цепочки индуцированных подграфов является самим графом Радо. Поскольку в каждом графе G i отсутствует хотя бы одна вершина из каждой i- графа Радо, не может быть i в Gi клики -клики .
Универсальность
[ редактировать ]Любой конечный или счетный без i -клик граф H можно найти как индуцированный подграф Gi , строя его по одной вершине за раз, добавляя на каждом шаге вершину, чьи ранние соседи в Gi H. совпадают с множеством ранних соседей графа соответствующая вершина в H . То есть G i является универсальным графом для семейства i -графов без клик.
Поскольку существуют i графы без -клик сколь угодно большим хроматическим числом , графы Хенсона имеют бесконечное хроматическое число. Более строго, если граф Хенсона G i разбит на любое конечное число индуцированных подграфов, то по крайней мере один из этих подграфов включает в себя все i -бескликовые конечные графы как индуцированные подграфы. [1]
Симметрия
[ редактировать ]Как и граф Радо, G 3 содержит двунаправленный гамильтонов путь , такой, что любая симметрия пути является симметрией всего графа. Однако это неверно для Gi , когда i > 3 : для этих графов каждый автоморфизм графа имеет более одной орбиты. [1]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д Хенсон, К. Уорд (1971), «Семейство счетных однородных графов», Pacific Journal of Mathematics , 38 : 69–83, doi : 10.2140/pjm.1971.38.69 , MR 0304242 .